Let G₁ and G₂ be two CFGs over Σ = {0, 1}, such that: G₁: X → 0X1 | XX | ε G₂:…
Let G₁ and G₂ be two CFGs over Σ = {0, 1}, such that:
G₁: X → 0X1 | XX | ε
G₂: X → 0X1X | 0X1 | 01X | 01
Consider the following statements:
S₁: Both G₁ and G₂ derive the same language.
S₂: G₁ is unambiguous while G₂ is ambiguous.
S₃: G₁ is LL(1) while G₂ is not LL(1).
Select the correct option:
Answer: D. All S₁, S₂, and S₃ are false. — Analyze each statement separately. S₁ is false. G₁ can derive ε directly using X → ε. In G₂, every production starts with 0 and produces at least one…
- A.
All S₁, S₂, and S₃ are true.
- B.
S₁ is true, while S₂ and S₃ are false.
- C.
S₁ and S₃ are true, while S₂ is false.
- D.
All S₁, S₂, and S₃ are false.
Attempted by 14 students.
Show answer & explanation
Correct answer: D
Analyze each statement separately.
S₁ is false. G₁ can derive ε directly using X → ε. In G₂, every production starts with 0 and produces at least one terminal, so ε cannot be derived. Therefore, G₁ and G₂ do not derive the same language.
S₂ is false. G₁ is ambiguous because of the concatenation production X → XX. For example, a string such as 010101 can be split as (01)(0101) or as (0101)(01), giving different parse trees. Thus G₁ is not unambiguous.
S₃ is false. An LL(1) grammar cannot be left-recursive or ambiguous. G₁ has direct left recursion through X → XX and is ambiguous, so G₁ is not LL(1). Therefore, the statement “G₁ is LL(1) while G₂ is not LL(1)” is false.
Hence S₁, S₂, and S₃ are all false, so option D is correct.