UGC NET CSE | December 2013 | Part 3 | Question: 21

Question

Given the following statements:

$S_1: \text{ The grammars }S \rightarrow asb \mid bsa \mid ss \mid a \text{ and } S \rightarrow asb \mid bsa \mid a$ are not equivalent.

$S_2: \text{ The grammars }S \rightarrow ss \mid sss \mid asb \mid bsa \mid \lambda \text{ and } S \rightarrow ss \mid asb \mid bsa \mid \lambda $ are equivalent.

• A. $S_1$ is correct and $S_2$ is not correct 
• B. Both $S_1$ ad $S_2$ are correct
• C. $S_1$ is not correct and $S_2$ is correct
• D. Both $S_1$ ad $S_2$ are not correct

Answer 1

Both are correct. 

S1: The grammars S→asb∣bsa∣ss∣a and S→asb∣bsa∣a are not equivalent b/c aa is not accepted by second.

S2:  second is also true.