What is the automaton recognising the language generated by G?

Question

Why is B not accepted as an answer?:

1. S --> 0A
2. A --> 0A
3. A --> 1B
4. B --> 1B
5. B --> e

Which ends up in the state of the automata is in the accept state.

Answer 1

It’s not hard to see that the grammar generates the language $L=\{0^m1^n:m,n\ge 1\}$. As peter.petrov notes in his answer, the automaton B accepts $010$, which is not in $L$. It also accepts $0$, which is not in $L$. To fix it to accept $L$, you’d have to make two changes:

• $q_1$ cannot be an acceptor state, because $0\notin L$, and you cannot have a $0$-transition from $q_2$ to $q_1$, since no word with a $0$ after a $1$ belongs to $L$.

And when you’ve made those changes, you have the automaton C, which does indeed recognize $L$.

As an exercise you might try to see why

• A accepts $\big\{1w:w\in\{0,1\}^*\big\}$, the language of all words over $\{0,1\}$ beginning with $1$;
• B accepts $\big\{0w:w\in\{0,1\}^*\big\}$, the language of all words over $\{0,1\}$ beginning with $0$; and
• D accepts the language of all words beginning with a $0$ and alternating $0$s and $1$s.

Answer 2

Because $B \rightarrow 0A$ is not a rule/production from the grammar.
The automata B would recognize the word $010$ but this word is not part of the language.