CODEWITHSUNDEEP
regexautomatadfa
Govs
Govs

Reputation: 13

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?

Upvotes: 1

Views: 27462

Answers (3)

Devanshu
Devanshu

Reputation: 1

Here is FA of not ending with '01' and the Regular Language is ((0+1)*(00+11+10)):

Image of this state diagram

Upvotes: 0

nhahtdh
nhahtdh

Reputation: 56809

You should at least come up with this DFA:

Then use the steps described here to solve for the regular expression.

R1 = 1R1 + 0R2 +       λ
R2 =       0R2 + 1R3 + λ
R3 = 1R1 + 0R2

The rest is left to you as an exercise.

Upvotes: 3

Amadan
Amadan

Reputation: 198294

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.

Upvotes: 3

Related Questions