Test: Context Free Language- 1


Test Description

10 Questions MCQ Test GATE Computer Science Engineering(CSE) 2023 Mock Test Series | Test: Context Free Language- 1

Test: Context Free Language- 1 for Computer Science Engineering (CSE) 2023 is part of GATE Computer Science Engineering(CSE) 2023 Mock Test Series preparation. The Test: Context Free Language- 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Context Free Language- 1 MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Context Free Language- 1 below.
Solutions of Test: Context Free Language- 1 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2023 Mock Test Series for Computer Science Engineering (CSE) & Test: Context Free Language- 1 solutions in Hindi for GATE Computer Science Engineering(CSE) 2023 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Context Free Language- 1 | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2023 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Context Free Language- 1 - Question 1

Which of the following languages is generated by the given grammar?

Detailed Solution for Test: Context Free Language- 1 - Question 1

Test: Context Free Language- 1 - Question 2

Consider the following context-free grammars;

Detailed Solution for Test: Context Free Language- 1 - Question 2

G1 results in strings b, ab, bb, aab, abb, bbb, ... i.e 

(and because only a's are not possible but only b's are)

G2 result in strings a, b, aa, ab, bb, aaa, aab, abb, bbb ... i.e

(or because only b's is possible
b,bb,bbb, , only a's are possible)

Test: Context Free Language- 1 - Question 3

Consider the following languages:

Which one of the following is TRUE?

Detailed Solution for Test: Context Free Language- 1 - Question 3

 is Context-free language

(push  into stack, then push  into stack , read  and pop  , when no  left on stack, keep reading  and pop
 , when no c's left in input , and stack is empty, then accepted).

is Context-sensitive language and not context-free. (cannot implemented by one stack)

 

Test: Context Free Language- 1 - Question 4

A context-free grammar is ambiguous if

Detailed Solution for Test: Context Free Language- 1 - Question 4

an ambiguous grammar produces more than one parse tree for any string.. that's B..

*Multiple options can be correct
Test: Context Free Language- 1 - Question 5

02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: (xix) Context-free languages are

Detailed Solution for Test: Context Free Language- 1 - Question 5

Context Free languages are not closed under intersection and complementation.

Test: Context Free Language- 1 - Question 6

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

If G is a context free grammar and  is a string of lengthl  in L(G), how long is a derivation of ω in G, if G is in Chomsky normal form?

Detailed Solution for Test: Context Free Language- 1 - Question 6

Chomsky Normal Form (If all of its production rules are of the form):

where A, B and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), namely, the language produced by the context-free grammar G. 

Applying productions of the first form will increase the number of nonterminals from k to k+1 since you replace one
nonterminal (-1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since you start with one nonterminal, this means you need to do l-1 productions of the first form. You then need l more of the second form to convert the
nonterminals to terminals, giving a total of l+(l-1) = (2l-1) productions.

Test: Context Free Language- 1 - Question 7

Which of the following definitions below generate the same language as L , where 

Detailed Solution for Test: Context Free Language- 1 - Question 7

In the other two you can have any number of x and y. There is no such restriction over the number of both being equal.

Test: Context Free Language- 1 - Question 8

If L1 and L2 are context free languages and  a regular set, one of the languages below is not necessarily a context free language. Which one?

Detailed Solution for Test: Context Free Language- 1 - Question 8

CFL's are not closed under intersection.

Test: Context Free Language- 1 - Question 9

Define a context free languages    for some υ in    ( in other words, (L) is the set of prefixes of L).

Let    is nonempty snd has an equal number of 0's and 1's}

Then  is

Detailed Solution for Test: Context Free Language- 1 - Question 9

 Because for any binary string of 0's and 1's we can append another string to make it contain equal
number of 0's and 1's. i.e., any string over {0,1} is a prefix of a string in L.

Example:

01111 - is prefix of 011110000 which is in L.
1111- is prefix of 11110000 which is in L.
01010- is prefix of 010101 which is in L.

 

Test: Context Free Language- 1 - Question 10

Context-free languages are closed under:

Detailed Solution for Test: Context Free Language- 1 - Question 10

Cfl are not closed under intersection and complement now choose the correct option so b)union and klenne closure

Information about Test: Context Free Language- 1 Page
In this test you can find the Exam questions for Test: Context Free Language- 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Context Free Language- 1, EduRev gives you an ample number of Online tests for practice
Download as PDF

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!
(Scan QR code)