Im not sure if I am understanding this question correctly. Its a problem without a solution in my text.

Starting with 1, and at least 01 or at least 010 or both these substrings..... So a regular expression will be given by: $1(0+1)^*01010(0+1)^* + 1(0+1)^*01001(0+1)^* + 1(0+1)^*010(0+1)^* + 1(0+1)^*01(0+1)^* = M$

But then surely $M = 1(0+1)^*01(0+1)^*$ ???

And then the NFA can simply be drawn as a three state NFA with starting state joined by edge $"1"$ to state B then joined by edge 01 to final state. And obviously there will be $0,1$ loops on state B and the final state?

Did I miss something? Perhaps the both implies it should be $M = 1(0+1)^*01010(0+1)^* + 1(0+1)^*01001(0+1)^* $

Do i need join state B with edges $"01","010","01010" and"01001"$ to the final state?

I would draw the graph but I cant find out how to do such things here. Its only a 3 state NFA regardless of the edges. I know that much :)

I think im getting confused with these "or" parts of the question.

  • $\begingroup$ Crosspost with math.stackexchange.com/questions/1412382/… $\endgroup$ – J.-E. Pin Aug 28 '15 at 9:28
  • 1
    $\begingroup$ $P \lor (P \land Q) \equiv P $ $\endgroup$ – André Souza Lemos Aug 28 '15 at 11:51
  • $\begingroup$ How are the "brackets" in this question? It might be: (start with 1 and having 01) or (having 010) or both. The "or both" is not necessary, as that is the common interpretation of "or". $\endgroup$ – Hendrik Jan Sep 5 '15 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.