Q79.Marks: +2.0UGC NET Paper 2: Computer Science and Application 26th June 2025 Shift 1
Which of the following Grammars is/are only Context Free?
A) S -> Ab
B) S -> Ab
aS -> aA
A -> Sa
A -> a
A -> a
C) S -> AS
S -> aA
D) S -> Ab
A -> a
S -> aA
A -> a
E) s -> sb
A -> Aa
A -> epsilon
Choose the correct answer from the options given below:
1.A, B Only
2. C, D Only✓ Correct
3. C, E Only
4.A, B, D, E Only
Solution
The correct answer isOption 2) C, D Only
What “only Context-Free” means
A context-free grammar (CFG) has productions of the form V → α where the left side is a single variable and α is any string of variables/terminals.
A regular grammar (a proper subset of CFGs) must be right-linear (V → a or V → aW) or left-linear (V → a or V → Wa) and must not mix both directions in one grammar. Regular grammars generate regular languages.
“Only context-free” here means: context-free but not regular.
Check each grammar
A.S → Ab
Left linear: a variable followed by a terminal (Ab).
This is consistent with a regular (left-linear) form. Even if there were no further rules (so the language is empty), the language is still regular. Hence not “only CF”.
B.S → Ab, aS → aA, A → Sa, A → a
The production aS → aA has a left side that is not a single variable. Therefore this grammar is not context-free (it is an unrestricted/context-sensitive rule).
So B cannot be “only CF”.
C.S → AS, S → aA
Left sides are single variables ⇒ CFG.
The rule S → AS contains two variables on the right; such a rule cannot appear in a regular grammar.
Therefore C is context-free but not regular ⇒ only CF.
D.S → Ab, S → aA, A → a
All left sides are single variables ⇒ CFG.
It mixes left-linear (S → Ab) and right-linear (S → aA) forms in the same grammar. Such mixing in general yields a language that is not regular (unless in a trivial degenerate case).
Hence D is context-free but not regular ⇒ only CF.
E.S → Sb, A → Aa, A → ε
All productions are left-linear or ε; this is a regular grammar (generates a regular language). (If S is the start symbol, the language from S is empty; empty language is regular. If the start were A, it generates a*, also regular.)
Therefore E is regular, not “only CF”.
Conclusion
The grammars that are context-free but not regular are C and D only.