Question 66
Which language is generated by S -> aSb | $\epsilon$?
Detailed Solution
Each recursive step adds one a and one b; $\epsilon gives$$n=0$.
✓ Saved
GATE CSE Context-Free Languages, Grammars & Pushdown Automata – TOC Practice Test | Set 1
Your score
0/100
0 answered
Correct 0
Incorrect 0
Unanswered 100
Accuracy 0%
Question 67
In Greibach Normal Form, a production has which general form?
Detailed Solution
GNF productions begin with exactly one terminal followed by zero or more nonterminals.
✓ Saved
Question 68
Which normal form requires productions of the form A -> BC or A -> a, with the usual special exception S -> $\epsilon$ when $\epsilon$ is in the language?
Detailed Solution
CNF uses A -> BC and A -> a, with a possible start-symbol $\epsilon rule under$ the standard convention.
✓ Saved
Question 69
Which statement about the CFL pumping lemma is false?
Detailed Solution
The lemma asserts existence of a suitable decomposition, not that every decomposition works.
✓ Saved
Question 70
Which language is not context-free?
Detailed Solution
Equal counts of three separated symbols cannot be enforced by a single stack; this language is not CFL.
✓ Saved