# Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the language of this figures (nfa, regular expression and grammar):

• Why do you think the languages are not the same? What languages do you get? – FrankW Oct 14 '14 at 11:27
• The regular expression (which, by the way can be simplified to $(a\mid b)b^*$) does indeed denote $L(M)$. However, your grammar can't derive $b$, which is in $L(M)$. It's not at all clear to me how you came up with the grammar; was it ad hoc or did you follow any systematic method? (There is a systematic way to produce a grammar from a finite automaton; it's in many intro theory texts.) – Rick Decker Oct 14 '14 at 14:41

We'll describe, in words, the languages encoded in each representation. Then, we'll see whether we end up with equivalent languages.

We'll start with the regular expression. This regular expression says: all strings that start with an $a$ or a $b$, followed by any number of repetitions of either of the strings $b$ or $bb$. Note that the $bb$ is completely superfluous in this definition since we can always just choose $b$ twice in a row. So this language is really "either an $a$ or a $b$, followed by any number of $b$s.

Now, for the automaton. The first observation is that the only way we can get an $a$ is if it's the first symbol we see; that's the only place an appropriate transition is defined and we never return to the initial state. We don't need to see an $a$ to accept; we can see a $b$ instead and accept (both $a$ and $b$ are accepted by the automaton). Now, how many $b$s can we see and still accept? Suppose the NFA always goes to state $2$ after the first input symbol (why not? it's an NFA). If we:

• see no more $b$s, we are in an accepting state... so we can see no $b$s and accept
• see one more $b$, we can go to state $4$ and accept
• see two more $b$s, we can go to state $3$ and then return to state $2$ where we accept
• more than two $b$s, we can go to state $3$, back to state $2$, and then we're in exactly the same situation as we were earlier, except now we have 2 fewer $b$s to worry about processing.

This should convince you that we can, in fact, see any number of $b$s after seeing either an $a$ or a $b$. Notice that we get the same thing as we did for the regular expression.

Now for the grammar. We note that the only way to produce a string with an $a$ is to use the production $S \rightarrow aAB$, so if we have a string with an $a$, it starts with an $a$ and that's the only $a$ in the string. In this case, we can always choose $B \rightarrow \epsilon$ and use the productions for $A$ to get any string of $b$s.

However - it appears your concerns were justified. Consider the other production for $S$ - $S \rightarrow bAb$. This is the only way we can get a string that starts with $b$. This production also says that any string that starts with a $b$ must have at least two $b$s in it - one at the front, and a different one at the back. In particular, we cannot get the string $b$ from this grammar. But this string is assuredly in the languages of the RE and automaton.

Therefore: $L(r) = L(M) \neq L(G)$.

• It's not hard to construct a regular grammar for this language: $S\rightarrow aT\mid bT, T\rightarrow bT\mid\epsilon$. – Rick Decker Oct 15 '14 at 3:22