Test: Context Free Language- 1 - Computer Science Engineering (CSE) MCQ

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)

 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)

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

Context Free languages are not closed under intersection and complementation.

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.

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.

CFL's are not closed under intersection.

 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.

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