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