Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to understand the answer here for FA that accepts only the words baa, ab, abb and no other strings longer or shorter. I understand where they got baa and ab but how did they get it to have abb ?

enter image description here

If anyone has another way to do this I would appreciate it... This is confusing to me with having a q7 state here.

share|cite|improve this question
The $q7$ state is called a "dead" state: once the machine gets into state q7, it is stuck there, because there is no transition out of q7. No computation that enters q7 can be an accepting computation. That is how we ensure that the machine will not accept any strings other than ab, abb, and baa. – MJD Mar 1 '14 at 20:08
when it says no other strings, that doesn't make sense cause I can go from q0,q1 to q7 and that will give me aa and it should be any other string – Bob Mar 1 '14 at 20:12
The machine does not accept aa because when it has finished reading aa, it is in state $q7$, which is not an accepting state. – MJD Mar 1 '14 at 20:12
that makes sense – Bob Mar 1 '14 at 20:14
up vote 8 down vote accepted

I understand where they got baa and ab but how did they get it to have abb ?

Just follow the arrows. "a" takes you to q1, then "b" takes you to q2, and another "b" takes you to q3, which is an accepting state.

this is confusing to me with having a q7 state here.

The q7 represents a failure state. Once the automaton enters that, it can't leave, so it will never accept that input string.

share|cite|improve this answer
I thought you couldn't pass from q2 into q3 because q2 is an ending state ? – Bob Mar 1 '14 at 20:08
Sure you can go out of q2. There's an arrow going out of it. (Don't think of q2 as an ending state --- the program does NOT terminate once it enters q2. It is merely that when the program is in q2, it can accept the input string so far. Think of q2 as an "accepting state".) – Newb Mar 1 '14 at 20:10
@Ris The machine does not stop once it gets to $q2$, even though $q2$ is sometimes called a "final" state. (This is a bad term, but that's what some people call it.) The machine continues until it reads the end of the input string. Then, if the current state is $q2, q3, $ or $q6$, the machine accepts the input. – MJD Mar 1 '14 at 20:11
thanks for your if I didn't have q7 state it would still be right ? – Bob Mar 1 '14 at 20:15

Expanding on Newb's point, you can think of Q7 as a 'trap' - the automaton can never escape, since both A and B lead back to Q7. It is necessary so that all strings are valid inputs to the FA, acting as a 'catch-all' for strings longer than four characters; however, as we've noted before, only ab, abb, and baa will be accepted.

share|cite|improve this answer

as you want to draw a NFA, trap state is not necessary. but, if you want to draw a DFA, as you know, all states should have exactly one vertex going out of each state. so, we are forced to draw a new state(named TRAP), and transfer all unused vertex to that state. in your question, for example, state q3 haven't outgoing vertex by 'a' , 'b' and it is not a DFA. to make this machine DFA, we should add vertex with label 'a' , 'b' to this state. but, we don't need these transitions to accept strings. so we guide them to trap. good luck

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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