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

Consider the following Context Free Grammar (G):

S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x

Variable = { S, A, B, C, D }

Terminals = { +, *, [, ], x }

Identify the correct statement from the following.

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

Show answer & explanation

Correct answer: C. [[x * x] + x] is a valid sentence of this grammar

Explanation

The grammar is not left recursive, since every production's right-hand side begins with a terminal or with a nonterminal whose own expansions start with a terminal, never recursively with itself (statement 1 false). No nonterminal's alternatives share a common prefix (B and D each choose between a terminal-led alternative and ε, and C chooses between '[' and 'x'), so no left factoring is needed (statement 2 false). The string [[x*x]+x] is derivable: the outer C → [S] wraps an inner S → AB where A → CD gives 'x*x' (via C → x, D → *CD → *x) and B → +AB supplies '+x', so S ⇒ [x*x]+x and the outer C-wrapping gives [[x*x]+x] (statement 3 true). "SLR(0)" is not a standard parser class (parser types are LR(0), SLR(1), LALR(1), canonical LR(1)), so statement 4 is not valid. The correct statement is [[x*x]+x] is a valid sentence of this grammar.

More Theory of Computation and Compilers questions