Test: Context Free Language- 1

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

This mock test of Test: Context Free Language- 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Context Free Language- 1 (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Context Free Language- 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Context Free Language- 1 exercise for a better result in the exam. You can find other Test: Context Free Language- 1 extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.

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



Consider the following context-free grammars;


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)


Consider the following languages:

Which one of the following is TRUE?


 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)



A context-free grammar is ambiguous if


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

*Multiple options can be correct

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


Context Free languages are not closed under intersection and complementation.


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?


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.


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


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.


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?


CFL's are not closed under intersection.


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


 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.


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.



Context-free languages are closed under:


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

Related tests