Monday, 3 December 2012

Converting state machines to regular expressions

Last week's tutorial/lecture finally made it clear how to translate a state machine to a regular expression (and vice versa) in practice. I liked being about to actually do it (rather than just understand it's possible in principle). For example:


Starting with this machine, we can remove the non-starting, non-accepting state:


And at this point it becomes clear the strings which will drive the machine to the accepting state. Namely, the regular expression R for this machine is: R = (10*1+0)(1*0(10*1+0))*. As you can see, even for such a simple machine, the expression is pretty nasty (but the important thing is, it's possible)!

No comments:

Post a Comment