## Contest-Free-Grammar

 Question 1

Consider the following context-free 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?

 A {(ab)n (cb)n│n ≥ 1} B {(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1} C {(ab)n (cbm)n│m,n ≥ 1} D {(ab)n (cbn)m│m,n ≥ 1}
Theory-of-Computation       Contest-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)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
 Question 2

Which of the following statements are true? I.Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa II.All e-productions can be removed from any context-free grammar by suitable transformations III.The language generated by a context-free grammar all of whose productions are of the form X ® w or X ® wY a non-terminal), is always regular (where, w is a string of  erminals and Y is IV.The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees
 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       Contest-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
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 non-terminals and 0 and 1 are the terminals. The language generated by this grammar is
 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       Contest-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 CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S→aS∣A A→aAb∣bAa∣ϵ Which of the following strings is generated by the grammar above?
 A aabbaba B aabaaba C abababb D aabbaab
Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
Question 4 Explanation:
S→aS
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 non-terminal 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?
 A 6 and 1 B 6 and 2 C 7 and 2 D 4 and 2
Theory-of-Computation       Contest-Free-Grammar       Gate 2008-IT
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.
 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?
 A I only B I and III only C II and III only D I, II and III
Theory-of-Computation       Contest-Free-Grammar       Gate-2006
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:
 Question 7
In the context-free 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?
 A aaaa B baba C abba D babaaabab
Theory-of-Computation       Contest-Free-Grammar       Gate 2006-IT
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.
 Question 8
In the context-free 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 ((a + b)* b)* B {ambn | m ≤ n} C {ambn | m = n} D a* b*
Theory-of-Computation       Contest-Free-Grammar       Gate 2006-IT
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.
 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?
 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       Contest-Free-Grammar       Gate-2003
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'.
 Question 10

 A FOLLOW(A) and LFOLLOW (A) may be different. B FOLLOW(A) and RFOLLOW (A) are always the same. C All the three sets are identical. D All the three sets are different. E Both A and B
Theory-of-Computation       Contest-Free-Grammar       Gate-1992
Question 10 Explanation: