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

enter image description here

  • 1
    $\begingroup$ Why do you think the languages are not the same? What languages do you get? $\endgroup$ – FrankW Oct 14 '14 at 11:27
  • 1
    $\begingroup$ 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.) $\endgroup$ – 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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.