ContestFreeGrammar
Question 1 
Consider the following contextfree grammar over the alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT  abcT
T → bT  b
Which one of the following represents the language generated by the above grammar?
{(ab)^{n} (cb)^{n}│n ≥ 1}  
{(ab)^{n} cb^{(m1 )} cb^{(m2 )}…cb^{(mn )}│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^{(m1 )} cb^{(m2 )}…cb^{(mn )}│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^{(m1 )} cb^{(m2 )}…cb^{(mn )}│n,m_{1},m_{2},…,m_{n} ≥ 1}
Question 2 
Which of the following statements are true?
I.Every leftrecursive grammar can be converted to a rightrecursive grammar and viceversa
II.All eproductions can be removed from any contextfree grammar by suitable transformations
III.The language generated by a contextfree grammar all of whose productions are of the form X ® w or X ® wY a nonterminal), is always regular (where, w is a string of erminals and Y is
IV.The derivation trees of strings generated by a contextfree grammar in Chomsky Normal Form are always binary trees
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 
Consider a CFG with the following productions. S → AA  B A → 0A  A0  1 B → 0B00  1 S is the start symbol, A and B are nonterminals and 0 and 1 are the terminals. The language generated by this grammar is
{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 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S→aS∣A
A→aAb∣bAa∣ϵ
Which of the following strings is generated by the grammar above?
aabbaba  
aabaaba  
abababb  
aabbaab 
Question 4 Explanation:
S→aS
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
S→aA
S→aaAb
S→aabAab
S→aabbAaab
S→aabbaab
Question 5 
A CFG G is given with the following productions where S is the start symbol, A is a nonterminal and a and b are terminals.
S→aS∣A
A→aAb∣bAa∣ϵ
For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?
6 and 1  
6 and 2  
7 and 2  
4 and 2 
Question 5 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 6 
Consider the following statements about the context free grammar
G = {S → SS, S → ab, S → ba, S → Ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
I only  
I and III only
 
II and III only
 
I, II and III

Question 6 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 7 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa  bSb  a  b  ϵ Which of the following strings is NOT generated by the grammar?
aaaa  
baba  
abba  
babaaabab 
Question 7 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 8 
In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string.
S → aSAb  ϵ
A → bA  ϵ
The grammar generates the language
((a + b)* b)*  
{a^{m}b^{n}  m ≤ n}  
{a^{m}b^{n}  m = n}  
a* b* 
Question 8 Explanation:
Option A generates string {aab, aaab, ........} which are not present in language hence this is wrong option.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
Option C&D:
→ abb accepted by given grammar but option C & D are not accepting.
Question 9 
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b  SS  ε Which of the following statements is true?
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 9 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 10 
FOLLOW(A) and LFOLLOW (A) may be different.  
FOLLOW(A) and RFOLLOW (A) are always the same.  
All the three sets are identical.  
All the three sets are different.
 
Both A and B 
Question 10 Explanation:
LFOLLOW may be different but RFOLLOW and FOLLOW will be same.
Question 11 
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 11 Explanation:
An ambiguous grammar produces more than one parse tree for some string.
There are 11 questions to complete.