Context Free Grammar
Question 1 
{(ab)^{n} (cb)^{n}│n≥1}  
{(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(m2 )}│n,m_{1},m_{2},…,m_{n}≥1}  
{(ab)^{n} (cb^{m})^{n}│m,n≥1}  
{(ab)^{n} (cb^{n})^{m}│m,n≥1} 
Question 1 Explanation:
T→ bT  b, this production will generate any number of b’s > 1
S→ abScT  abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc” .
For Ex:
Hence the language generated by the grammar is
L={(ab)^{n}cb^{m}_{1}cb^{m}_{2}...cb^{m}_{n}  n,m_{1},m_{2},...,m_{n}≥1}
S→ abScT  abcT, this production will generate equal number of “ab” and “c” and for every “abc” any number of b’s ( > 1) after “abc” .
For Ex:
Hence the language generated by the grammar is
L={(ab)^{n}cb^{m}_{1}cb^{m}_{2}...cb^{m}_{n}  n,m_{1},m_{2},...,m_{n}≥1}
Question 2 
I, II, III and IV  
II, III and IV only  
I, III and IV only  
I, II and IV only 
Question 2 Explanation:
Every left recursive grammar can be converted to a rightrecursive grammar and viceversa, the conversion of a left recursive grammar into right recursive is also known as eliminating left recursion from the grammar. Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar). Statement IV is also true, as in CNF the only productions allowed are of type:
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
A> BC
A> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 3 
{0^{n} 10^{2n}  n ≥ 1}  
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
{0^{i} 10^{j}  i, j ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ l}  
The set of all strings over {0, 1} containing at least two 0’s  
None of the above 
Question 3 Explanation:
S → AA  B
A → 0A  A0  1
B → 0B00  1
In this B → 0B00  1 which generates {0n 102n  n ≥0}
S → AA  B
A → 0A  A0  1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Nonterminal B i s generating the second part of B choice and AA is generating the first part.
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ 0}
A → 0A  A0  1
B → 0B00  1
In this B → 0B00  1 which generates {0n 102n  n ≥0}
S → AA  B
A → 0A  A0  1
Which generates 0A0A → 00A0A → 00101.
Which is suitable for B and D option. D is not correct because 00 is not generated by the given grammar. So only option B is left. Nonterminal B i s generating the second part of B choice and AA is generating the first part.
{0^{i} 10^{j} 10^{k}  i, j, k ≥ 0} ∪ {0^{n} 10^{2n}  n ≥ 0}
Question 4 
6 and 1  
6 and 2  
7 and 2  
4 and 2 
Question 4 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required
Only 1 parse tree is there.
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
⇒ 6 steps are required
Only 1 parse tree is there.
Question 5 
I only  
I and III only
 
II and III only
 
I, II and III

Question 5 Explanation:
Is ambiguous, as it has two parse tree for the string “abbaba”
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
G doesn’t product all strings of equal number of a’s and b’s, for ex: string “aabb” doesn’t generate by grammar G.
The language generated by G can be accepted by DPDA. We can notice that grammar G generates, a’s and b’s in pair, i.e. either “ab” or “ba”, so the strings in language are {ab, ba, abab, abba, baba, ….}
We can design the DPDA:
Question 6 
aaaa  
baba  
abba  
babaaabab 
Question 6 Explanation:
S → aSa  bSb  a  b  ϵ
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accpeted by S.
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accpeted by S.
Question 7 
G is not ambiguous
 
There exist x, y ∈ L(G) such that xy ∉ L(G)
 
There is a deterministic pushdown automaton that accepts L(G)  
We can find a deterministic finite state automaton that accepts L(G)

Question 7 Explanation:
a) False
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
Question 8 
A contextfree grammar is ambiguous if:
The grammar contains useless nonterminals.  
It produces more than one parse tree for some sentence.  
Some production has two non terminals side by side on the righthand side.  
None of the above. 
Question 8 Explanation:
An ambiguous grammar produces more than one parse tree for some string.
There are 8 questions to complete.