Consider the following statements about the context-free grammar: G = { S →…
Consider the following statements about the context-free grammar:
G = { S → SS, S → 01, S → 10, S → ε }
S₁: G is ambiguous.
S₂: G produces all strings with an equal number of 0s and 1s.
Select the correct option:
Answer: C. S₁ is correct, but S₂ is false. — S₁ is true. The grammar is ambiguous because S → SS allows different groupings of the same concatenation. For example, 011010 can be grouped as (01)(1010) or…
- A.
Both S₁ and S₂ are correct.
- B.
Both S₁ and S₂ are incorrect.
- C.
S₁ is correct, but S₂ is false.
- D.
S₁ is false, but S₂ is true.
Attempted by 80 students.
Show answer & explanation
Correct answer: C
S₁ is true. The grammar is ambiguous because S → SS allows different groupings of the same concatenation. For example, 011010 can be grouped as (01)(1010) or as (0110)(10), giving different parse trees.
S₂ is false. The grammar generates concatenations of the blocks 01 and 10, along with ε. Therefore every generated non-empty block contributes one 0 and one 1, but not every string with equal numbers of 0s and 1s is generated. For example, 0011 has two 0s and two 1s, but it cannot be formed as a concatenation of 01 and 10 blocks.
Thus S₁ is correct and S₂ is false, so option C is correct.