1

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?

Govs
  • 13
  • 1
  • 1
  • 3
  • Note that most answers will probably use the dialect of regular expression usual in programming languages, rather than mathematics - `a+b` to us means what `aa*b` means to you (`+` meaning "one or more repetitions of"), while we'd write your `a+b` as `a|b` (disjunction). – Amadan Oct 23 '14 at 04:23
  • Also, your first attempt is almost correct, just failing to match strings of length under 2: `"0"` and `"1"` should also match, as should empty string (`""`) that I forgot in my comment to Andrew Luo. This can be solved with simple disjunction. http://rubular.com/r/855DYj0lHb should let you see it in action - `^` and `$` anchor the beginning of line and the end of line, so you don't get matches from the middle. – Amadan Oct 23 '14 at 04:28

3 Answers3

3

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.

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • In programmer's dialect, you forgot the grouping `^([01]*(00|10|11)|0|1|)$` – nhahtdh Oct 23 '14 at 05:11
  • I believe this would actually be: `(0+1)*(00+10+11)+0+ε` As previously written, you could select a 0 from the star group and then select the 1 from the union. – bulletshot60 Jan 17 '19 at 19:50
  • @bulletshot60: I don't understand the comment, unless we disagree on priorities. What I wrote breaks down to `((0+1)*((00)+(10)+(11)))+0+1+ε`, with concatenation having the highest priority; so if you choose anything from the star group, the only thing you can concatenate to it are the two-digit options. There is no chance to select 0 from the star group, and 1 from the union. – Amadan Jan 18 '19 at 04:43
  • I see. Thanks for the clarification. – bulletshot60 Jan 19 '19 at 18:19
3

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.

Community
  • 1
  • 1
nhahtdh
  • 55,989
  • 15
  • 126
  • 162
0

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

Image of this state diagram

flyingfishcattle
  • 1,817
  • 3
  • 14
  • 25
Devanshu
  • 1