FA design examples

Advice when designing...

1) Have meaning for each state - It's the only memory an FA has.

2) First write just the part that accepts good strings.

3) Make sure your FA is legal. Double check that every state has an arrow out for each alphabet symbol and that their's a start state.

4) Try to break your solutions. Look for strings it accepts that it shouldn't. Look for strings that it rejects that it shouldn't.

Examples

Let the alphabet be {a,b}. The text descriptions are for http://ivanzuzak.info/noam/webapps/fsm_simulator/

Write a FA that accepts all the strings in {abba}

#alphabet
a
b
#states
0
1
2
3
4
5
#initial
0
#accepting
4
#transitions
0:a>1
0:b>5
1:b>2
1:a>5
2:b>3
2:a>5
3:a>4
3:b>5
4:a>5
4:b>5
5:a>5
5:b>5

Write a FA that accepts all the strings in { w ∈ {a,b}* : w has at least two a's }

x
#alphabet
a
b
#states
0
1
2
#initial
0
#accepting
2
#transitions
0:b>0
0:a>1
1:a>2
1:b>1
2:a>2
2:b>2

Write a FA that accepts all the strings in { w ∈ {a,b}* : w begins and ends in the same letter }

x
#alphabet
a
b
#states
0
aa
ab
ba
bb
#initial
0
#accepting
aa
bb
#transitions
0:a>aa
0:b>bb
aa:a>aa
aa:b>ab
bb:b>bb
bb:a>ba
ab:b>ab
ab:a>aa
ba:a>ba
ba:b>bb

Write a FA that accepts all the strings in { aⁿb^m : n odd and m even }

x
#alphabet
a
b
#states
ae
ao
bo
be
garb
#initial
ae
#accepting
be
ao
#transitions
ao:a>ae
ae:a>ao
ae:b>garb
ao:b>bo
bo:b>be
bo:a>garb
be:a>garb
be:b>bo
garb:a>garb
garb:b>garb