Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to remove the epsilon transition from following grammar: \begin{eqnarray} S & \rightarrow & A | B \\ A & \rightarrow & \epsilon \\ B & \rightarrow & aBa \\ B & \rightarrow & b \\ \end{eqnarray} This is the result of removing $\epsilon$ transition: \begin{eqnarray} S & \rightarrow & \epsilon | B \\ B & \rightarrow & aBa \\ B & \rightarrow & b \end{eqnarray}
My question is what's the difference between languages that accept these two grammars?
There is no difference. Both grammars describe the same language $$L = \{ \epsilon \} \cup \{ a^nba^n | \forall n > 0\}.$$
No difference. You can't re-choose the terminal $A$ after choosing it even once in your example.
