All mock tests are FREE till 31 December — register to save your progress

Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?
GrammarProductions
AS → Ab
aS → aA
A → a
BS → Ab
A → Sa
A → a
CS → AS
S → aA
A → a
DS → Ab
S → aA
A → a
ES → Sb
A → Aa
A → ε

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. C, D Only

Explanation

A has the rule aS → aA, whose left side has more than one symbol, so it is context-sensitive, not context-free. E (S → Sb, A → Aa, A → ε) is entirely left-linear, so it is a regular grammar. C has S → AS (two non-terminals on the right) and D mixes a left-linear rule S → Ab with a right-linear rule S → aA, so neither is a regular grammar; both are only context-free. (B is also context-free, but no option pairs it correctly, so C, D is the answer.)

More Theory of Computation and Compilers questions