Let G1 and G2 be two CFG G1: S → 0X1 | XX |ϵ X → S G2: S→0X1X | 0X1 | 01X X→S…
Let G1 and G2 be two CFG
G1: S → 0X1 | XX |ϵ
X → S
G2: S→0X1X | 0X1 | 01X
X→S | ϵ
Consider the statements:
S1: G1 and G2 derives the same language.
S2: G1 is ambiguous and G2 is unambiguous
S3: G1 is CLR(1).
Which of the above option is/are TRUE:
Answer: A. All S1, S2 and S3 — Correct answer: None of the statements is true. S1: G1 derives the empty string (S → ε), but G2 cannot derive ε because every production for S begins with the…
- A.
All S1, S2 and S3
- B.
Only S2
- C.
Only S1 and S3
- D.
Only S3
Attempted by 30 students.
Show answer & explanation
Correct answer: A
Correct answer: None of the statements is true.
S1: G1 derives the empty string (S → ε), but G2 cannot derive ε because every production for S begins with the terminal 0. Therefore the languages differ and S1 is false.
S2: G1 is ambiguous—for example ε has multiple derivations (S → ε and S → S S with both S → ε). G2 is also ambiguous: the string "01" can be derived in more than one way (for instance via S → 0X1 with X → ε and via S → 01X with X → ε). Thus the statement that G1 is ambiguous and G2 is unambiguous is false.
S3: G1 is not LR(1) (canonical LR(1)) because it is ambiguous, and LR(1) grammars must be unambiguous. Therefore S3 is false.
Conclusion: none of S1, S2, or S3 holds for the given grammars.