Finite state machine

Question

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.

Answer 1

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:

Answer 2

The diagram of FSM describes everything!