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 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):
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:
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)$.
