Tuesday, December 4, 2012
Converting Regular Expression to NFA
Labels:
GATE,
TOC,
TOC-Finite Automata
We can convert a regular expression to NFA by METHOD OF DECOMPOSITION
E.g. 1: For RE = r NFA will be
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
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment