## Context Free Grammar

 Question 1

 A {(ab)n (cb)n│n≥1} B {(ab)n cb(m1 ) cb(m2 )…cb(m2 )│n,m1,m2,…,mn≥1} C {(ab)n (cbm)n│m,n≥1} D {(ab)n (cbn)m│m,n≥1}
Theory Of Computation       Context Free Grammar       Gate 2017 set-01
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)ncbm1cbm2...cbmn | n,m1,m2,...,mn≥1}
 Question 2

 A I, II, III and IV B II, III and IV only C I, III and IV only D I, II and IV only
Theory of Computation        Context Free Grammar       Gate-2008
Question 2 Explanation:
Every left recursive grammar can be converted to a right-recursive grammar and vice-versa, 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.
 Question 3

 A {0n 102n | n ≥ 1} B {0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ l} C {0i 10j | i, j ≥ 0} ∪ {0n 102n | n ≥ l} D The set of all strings over {0, 1} containing at least two 0’s E None of the above
Theory of Computation        Context Free Grammar       Gate 2008-IT
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. Non-terminal B i s generating the second part of B choice and AA is generating the first part.
{0i 10j 10k | i, j, k ≥ 0} ∪ {0n 102n | n ≥ 0}
 Question 4

 A 6 and 1 B 6 and 2 C 7 and 2 D 4 and 2
Theory of Computation        Context Free Grammar       Gate 2008-IT
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.
 Question 5

 A I only B I and III only C II and III only D I, II and III
Theory of Computation        Context Free Grammar       Gate-2006
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:
 Question 6

 A aaaa B baba C abba D babaaabab
Theory of Computation        Context Free Grammar       Gate 2006-IT
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.
 Question 7

 A G is not ambiguous B There exist x, y ∈ L(G) such that xy ∉ L(G) C There is a deterministic pushdown automaton that accepts L(G) D We can find a deterministic finite state automaton that accepts L(G)
Theory of Computation        Context Free Grammar       Gate-2003
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'.
 Question 8
A context-free grammar is ambiguous if:
 A The grammar contains useless non-terminals. B It produces more than one parse tree for some sentence. C Some production has two non terminals side by side on the right-hand side. D None of the above.
Theory of Computation        Context Free Grammar       GATE-1987
Question 8 Explanation:
An ambiguous grammar produces more than one parse tree for some string.
There are 8 questions to complete.