3
$\begingroup$

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.

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

2 Answers 2

Reset to default
1
$\begingroup$

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: Jah mann

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Thumbnail
    Sep 28, 2015 at 10:31
1
$\begingroup$

The diagram of FSM describes everything! FSM on $\{a, b\} that accept strings with exactly one $b$ and an even number of $a$s.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .