Given the following statements: S₁: The grammars S → aSb | bSa | SS | a and S…
2013
Given the following statements:
S₁: The grammars S → aSb | bSa | SS | a and S → aSb | bSa | a are not equivalent
S₂: The grammars S → SS | SSS | aSb | bSa | λ and S → SS | aSb | bSa | λ are equivalent
Which of the following is true?
- A.
S₁ is correct and S₂ is not correct
- B.
Both S₁ and S₂ are correct
- C.
S₁ is not correct and S₂ is correct
- D.
Both S₁ and S₂ are not correct
Attempted by 22 students.
Show answer & explanation
Correct answer: B
For Statement S₁, Grammar 1 allows concatenation via SS, generating strings like "aa" where 'a' exceeds 'b'. Grammar 2 strictly maintains one more 'a' than 'b', making them non-equivalent. For Statement S₂, both grammars generate balanced strings with equal 'a' and 'b'. The production S → SSS is redundant given SS closure. Thus, both statements are correct.
A video solution is available for this question — log in and enroll to watch it.