regexautomatadfa

Regular Expression for Automata for Strings that do not end in 01

Automata for strings that do not end with 01.

I cannot obtain the regular expression for the Automata with alphabet={0,1} that generates the strings that do not end with 01.

Here is the state diagram:

State Diagram

I get this state diagram with the Visual Automata Simulator tool by Matthew McClintock, so I tested some strings like empty string e, "0","1","00","10","11" and the ones that do not end with 01, and it seems to work.

Can you help me to obtain the regular expression?. I didn't have formal introduction to computer automata theory, so I barely understand the concepts of dfa,nfa and the nomenclature is kind of strange to me.

I tried to obtained the regexp, one was:

(0+1)*(00+10+11)

but I no sure if that is correct.

Then according to the diagram I have tried things like:

1*(00*1+0+0*1)*+1(00*1+0*1)*

Or things like that. Do you know were can I test regular expressions?

Solution

  • As I said in the comments, you were pretty close in your first attempt. This should work:

    (0+1)*(00+10+11)+0+1+ε

    or, in programmer dialect,

    ^([01]*(00|10|11)|0|1|)$

    EDIT: Thank you nhahtdh, indeed I had.