0

dfa

What is the correct regular expression for this DFA?

I came up with the solution

0|1(0(0|1))*1*

The problem with my solution is, that it's not possible to use the q2->q2 and then loop through q1 and q2.

The correct answer according to the paper is

(0|1)(1|0(0|1))∗

This one looks false too, because it looks like its not possible to go q1->q2->q2.

So my question is, what is the correct regular expression and why. And why is my solution may wrong (maybe more errors than I already exposed to you)?

Robert
  • 21
  • Why don't you think the paper's answer is correct? We have a zero or a one followed by any number of either a one or a zero followed by a one or zero. That looks correct to me. – John Douma Feb 04 '24 at 07:56
  • @JohnDouma Try it going from q1->q2 with 0. And then we use the q2->q2 loop once. So the word is 01. The regular expression from the paper requires one or at least three letters. – Robert Feb 04 '24 at 07:59
  • The star applies to everything after the initial character. So, for example, $0111$ which stays in state $q2$ works. This is saying that we can't have an empty string; we require an initial character. After that, we can have any number of ones or any number of zero followed by anything. Basically, everytime we get a zero after the initial one, we need another character to get us back to $q2$. – John Douma Feb 04 '24 at 08:02
  • It may be clearer if you write it as $(0|1)(1|00|01)*$ – John Douma Feb 04 '24 at 08:12

1 Answers1

0

So the solution is fairly easy. I didn't read the answer from the paper correctly.

So (1|0(0|1))

is read 1 OR 0(0|1)

Robert
  • 21