Tuesday, December 4, 2012

Converting Regular Expression to NFA

We can convert a regular expression to NFA by METHOD OF DECOMPOSITION


Step 1: In this mechanism we need to take the given RE as a edge-label for the FA with 2 states: one is initial and other is final state i.e. we have to start a process with 2 state machine.
Step 2: Decompose the RE and keep on adding the states until the total RE is decomposed & then we get a NFA which is equivalent to the given RE.

E.g. 1: For RE = r       NFA will be 


E.g. 2: For RE = r1+r2       NFA will be


E.g. 3: For RE = r1.r2       NFA will be



E.g. 4: For RE = r*       NFA will be
E.g. 5: For RE = (r1 + r2)*       NFA will be

E.g. 6: For RE = (r1 . r2)*       NFA will be

E.g. 7: For RE = (a+ba)* b(aa)* ba*       NFA will be



No comments:

Post a Comment