in Theory of Computation
360 views
0 votes
0 votes

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:

in Theory of Computation
360 views

4 Comments

@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? 

0
0
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
1
1
edited by

@Shaik Masthan

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

0
0

Please log in or register to answer this question.

Related questions