Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I am learning about automata and finite state machines. Consider the following automaton, that accepts the word 'ab', does not have to be infinite, just once:

alphabet: 'a','b' states: 1,2, 3 (3 is the final state and 1 is the initial state)

transitions:

state 1, symbol a, state 2
state 2, symbol b, state 3

First part of my questions:

Question 1. Is it required to add self-loops at 1 for 'b', and a self-loop for 'a' at 2?

Question 2. What about at state 3(final)? Should I add self-loops for 'a' and 'b'?

I basically need to know, how to design my final state. So that even if my alphabet was expanded (say a, b, c), and I have a 'dump' state, with the following transitions:

state 1, symbol a, state 2
state 1, symbol b or c, state dump

state 2, symbol b, state 3
state 2 symbol a or c, state dump

Question 3. Now from final state 3, should I add a transition to dump state, with symbol values a,b,c ???

Your assistance is much appreciated.

share|improve this question
    
Your automaton is fine, you don't have to add anything. Of course you can add a dead state (outdegree = 0). –  saadtaame Feb 12 '13 at 19:03
    
1, 2. You don't have to show all possible transitions. Absent transitions generally imply rejection. So if you get b in state 1, and there is no loop for it, it means the input is rejected. 3. Yes, if you have a dump state. But you don't need to. –  Paresh Feb 12 '13 at 19:20
add comment

1 Answer

up vote 0 down vote accepted

Your original automaton is fine, it accepts the singleton $\{ab\}$. Here is a pictorial representation:

enter image description here

In the above automaton it's implicit that given a state and a letter for which there is no arrow going out of that state, then the automaton "crashes". If you want to be complete, you can add a dead state that absorbs strings that don't belong in the language. Here is the complete automaton:

enter image description here

If you add self-loops at 1 and/or 2, you will change the language that the automaton accepts. Look at this:

enter image description here

The self-loop at 1 labeled with $b$ changes the language to $\{ab, bab, bbab, bbbab, \dots\}$.

share|improve this answer
    
Thanks for all the comments provided and the great answer with images to help me understand :) –  Piotr L. Feb 13 '13 at 0:01
    
@PiotrL. The $d$ is a typo in the automata... Glad it helps. –  saadtaame Feb 13 '13 at 0:21
add comment

Your Answer

 
discard

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.