Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite state machine that recognizes word in the language(input alphabet, states, start state, state transition table, and accept states). Include a state digraph for the FSM.

L: For alphabet {a,b}, all strings that contain an odd number of a's and exactly one b.

If you could help me understand this more in depth, that would be amazing.

• I answered below, but maybe not to the depth you'd like, please let me know... ty Mar 28, 2014 at 3:13

You want a regular expression that is any number, $k$, of $a$'s, followed by a $b$, followed by:

• an even number of $a$'s if $k$ is odd.
• an odd number of $a$'s if $k$ is even.

So after some guessing...

$L = a (aa)^* b (aa)^* \ | \ (aa)^* b (aa)^* a$.

To do the FSM, you just add nodes as you need them... there's probably algorthms that can automatically output an FSM graph, but this example is small enough to brute-force.

Here's what I got:

• You have a couple of redundant states. $ab$ and $ba$ should take you to the same place, representing $(aa)^*$. So take $ab$ to the bottom right, say, and drop your two top right states. Sep 28, 2015 at 10:31

The diagram of FSM describes everything!