360 views

Convert the following regular expression (0+11)0*1 to NFA with e-transitions using the procedure given on pg. 66-67 Theorem 1.54 (Lemma 1.55) of the Introduction to Theory of Computation 3rd edition book by Michael Sipser.

I followed the example in the book, but what confuses me is when the Kleene star is added individually like 0*, how would we illustrate this?

This was my approach for just 0*1 part: @Shaik Masthan

I had another quick question, for the following regular expression:

(0 + 10 + 1 + (1+0)(0+1)*)* , I converted it to e-nfa by doing the following steps(drawing the e-nfa):  (0+1) → (0+1)* → (1+0) → (1+0)(0+1)* → 1 + (1+0)(0+1)* → 10 + 1 + (1+0)(0+1)* → 0 + 10 + 1 + (1+0)(0+1)* → (0 + 10 + 1 + (1+0)(0+1)*)*. Would this be a correct way to draw the e-nfa for this particular regular expression?

No problem with this approach.

But in Gate point of view, practicing NFA to RE is sufficient. If the question asking about NFA of a RE, You need to see the options (NFA's) and converting them into RE
edited

@Shaik Masthan

Thanks for the feedback, I am practicing both ways to get a good understanding.