# NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both

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.

• Crosspost with math.stackexchange.com/questions/1412382/… – J.-E. Pin Aug 28 '15 at 9:28
• $P \lor (P \land Q) \equiv P$ – André Souza Lemos Aug 28 '15 at 11:51
• 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". – Hendrik Jan Sep 5 '15 at 23:29