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
- What will be the FIRST(S) & FIRST(D)?
- The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
- Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?Grammar Productions A S → Ab aS → aA…
- Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a d…
- Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:State a b c →* q0 q1 q0 q0 q…
- Match List I with List IIList I List II A. Type 3 Grammar I. V → (V ∪ Σ)* B. Type 2 Grammar II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* C.…