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?
{(ab)n (cb)n│n ≥ 1}
{(ab)n cb(m1 ) cb(m2 )…cb(mn )│n,m1,m2,…,mn ≥ 1}
{(ab)n (cbm)n│m,n ≥ 1}
{(ab)n (cbn)m│m,n ≥ 1}
       Theory-of-Computation       Contest-Free-Grammar       GATE 2017 [Set-1]       Video-Explanation
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 \epsilon 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 (where, w is a string of terminals and Y is a non-terminal), is always regular
    IV. The derivation trees of strings generated by a context-free 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
       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.
There are 2 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact to get access