Equivalence Of Nfa And Dfa

Definition: Two finite accepters M1 and M2 are equivalent iff

L(M1 ) = L(M2 ) i.e., if both accept the same language.

Both DFA and NFA recognize the same class of languages. It is important to note that every NFA has an equivalent DFA. Let us illustrate the conversion of NDA to DFA through an example.

Example: Determine a deterministic Finite State Automaton from the given Nondeterministic FSA.

M = ({q0 , q1},{a, b}, , q0 ,{q1})

with the state table diagram for d given below.

Solution

Let M¢ = (Q¢, S,d¢, q¢ , F¢ ) 0 be a determine. Finite state automaton (DFA), where

Q¢ = {[q0 ], [q1 ], [q0 , q1 ], [ ]}, Æ

q¢0 = [q0]

and F¢ = {[q1 ], [q0 , q1 ]}

Please remember that [ ] denotes a single state. Let us now proceed to determine d¢ to be defined for the DFA.

Here any subset containing q1 is the final state in DFA. This is shown as below.

SKEDSOFT