If you want to make money online : Register now

[Solved]: Equivalence of some Automata & Language & NFA

, , No Comments
Problem Detail: 

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

Asked By : T. Jzmod

Answered By : Patrick87

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31910

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback