Scribd
Upload
15 views2 pages

NFA to DFA Conversion Algorithm Guide

The document describes the subset construction algorithm for converting a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA). The algorithm works by calculating the epsilon-closure of states, which are the states reachable via epsilon transitions. New DFA states are the epsilon closures of NFA states. Transitions are determined by taking the epsilon-closure of following an input symbol. The example shows calculating the epsilon closures of states for a given NFA and constructing the corresponding DFA.

Uploaded by

Sugata Ghosh
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
15 views2 pages

NFA to DFA Conversion Algorithm Guide

The document describes the subset construction algorithm for converting a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA). The algorithm works by calculating the epsilon-closure of states, which are the states reachable via epsilon transitions. New DFA states are the epsilon closures of NFA states. Transitions are determined by taking the epsilon-closure of following an input symbol. The example shows calculating the epsilon closures of states for a given NFA and constructing the corresponding DFA.

Uploaded by

Sugata Ghosh
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd

SUBSET CONSTRUCTION(CONVERSION OF NFA TO DFA)

(PIYUSH GOEL , 03CS3003 ) It is used for converting an NFA having epsilon transition into a DFA. The Algorithm for this is as follows:Let the DFA be D & its transition table be [Link] represents the states of the [Link] NFA be N. Initially e-closure(s){start state of NFA} is the only state in Dstate and it is unmarked. While there is an unmarked state T in Dstate do begin Mark T; For each input symbol a do begin U=e-closure(move(T,a)); If U is not in Dstates then Add U as unmarked state to Dstate. Dtran[T,a]=U; End End A state D is an accepting state if it is a set of NFA containing atleast one accepting state of the N. The following example was shown:NFA given was:INPUT(TERMINAL OR E(EPSILON)) a STATES ->0(s) 1 2 3 4 5 6 7 8 9 10(f) {3} {8} b {5} {9} {10} e (Epsilon) {1,7} {4,2} {6} {6} {1,7} states

s denotes the start state f denotes it is a final state The e-closures are calculated as follows:

eclosure(0)={0,1,2,4,7}=A=start state in corresponding DFA eclosure(move(A,a))={1,2,3,4,6,7,8}=B eclosure(move(A,b))={1,2,4,5,6,7}=C eclosure(move(B,a))=B eclosure(move(B,b))={1,2,5,6,7,9}=D eclosure(move(C,a))=B eclosure(move(C,b))=C eclosure(move(D,a))=B eclosure(move(D,b))={1,2,4,5,6,7,10}=E=final state eclosure(move(E,a))=B eclosure(move(E,b))=C The Corresponding DFA is:INPUT(TERMINAL) a STATE ->A B C D E B B B B B C D C E(final) C b

You might also like