80 9 Theory of Computer Science
- - - - - - - - - - - - - - - - - - -
3.7 THE EQUIVALENCE OF DFA AND NDFA
We naturally try to find the relation between DFA and NDFA. Intuitively we
now feel that:
(i) A DFA can simulate the behaviour of NDFA by increasing the number
of states. (In other words. a DFA (Q, L, 8, qQ, F) can be viewed as an
NDFA (Q, L, 8', qQ, F) by defining 8'(q, a) = {8(q, a)}.)
Oi) Any NDFA is a more general machine without being more powelfuL
We now give a theorem on equivalence of DFA and NDFA.
Theorem 3.1 For every NDFA, there exists a DFA which simulates the
behaviour of NDFA. Alternatively, if L is the set accepted by NDFA, then there
exists a DFA which also accepts L.
Proof Let M = (Q, L, 8, qQ, F) be an NDFA accepting L. We construct a DFA
M' as:
M' = (Q', L, 8, (/o, F')
where
(i) Q' = 2
Q (any state in Q' is denoted by [qio q2, .... q;], where qio q2,
.... qj E Q):
(ii) q'0 = [clo]; and
(iii) r is the set of all subsets of Q containing an element of F.
Before defining 8'. let us look at the construction of Q', q'o and r. M is
initially at qo. But on application of an input symbol, say a, M can reach any
of the states 8(qo, a). To describe M, just after the application of the input
symbol a. we require all the possible states that M can reach after the
application of a. So, lvI' has to remember all these possible states at any instant
of time. Hence the states of M' are defined as subsets of Q. As M starts with
the initial state qo, q'o is defined as [qo]. A string w belongs to T(M) if a final
state is one of the possible states that M reaches on processing w. So, a final
state in M' (i.e. an element of F') is any subset of Q containing some final
state of M.
Now we can define 8':
(iv) 8'([qb q2. .... qi], a) = 8(q[, a) u 8(q2, a) u '" U 8(qi' a).
Equivalently.
if and only if
8({ql' ..., q;}, a) = {PI, P2 • ..., Pi}'
Before proving L = T(M'), we prove an auxiliary result
8'(q'o, x) = [qj, .. '. q;],
if and only if 8(qo, x) = {qj, "" q;} for all x in P.
We prove by induction on Ix I. the 'if part. i.e.
8'(q'o. x) = [qJ' q2. , ... q;]
if 8(qo. x) = {qJ ..... q;}.
(3.4)
(3.5)
- - - - - - - - - - - - - - - - - - -
3.7 THE EQUIVALENCE OF DFA AND NDFA
We naturally try to find the relation between DFA and NDFA. Intuitively we
now feel that:
(i) A DFA can simulate the behaviour of NDFA by increasing the number
of states. (In other words. a DFA (Q, L, 8, qQ, F) can be viewed as an
NDFA (Q, L, 8', qQ, F) by defining 8'(q, a) = {8(q, a)}.)
Oi) Any NDFA is a more general machine without being more powelfuL
We now give a theorem on equivalence of DFA and NDFA.
Theorem 3.1 For every NDFA, there exists a DFA which simulates the
behaviour of NDFA. Alternatively, if L is the set accepted by NDFA, then there
exists a DFA which also accepts L.
Proof Let M = (Q, L, 8, qQ, F) be an NDFA accepting L. We construct a DFA
M' as:
M' = (Q', L, 8, (/o, F')
where
(i) Q' = 2
Q (any state in Q' is denoted by [qio q2, .... q;], where qio q2,
.... qj E Q):
(ii) q'0 = [clo]; and
(iii) r is the set of all subsets of Q containing an element of F.
Before defining 8'. let us look at the construction of Q', q'o and r. M is
initially at qo. But on application of an input symbol, say a, M can reach any
of the states 8(qo, a). To describe M, just after the application of the input
symbol a. we require all the possible states that M can reach after the
application of a. So, lvI' has to remember all these possible states at any instant
of time. Hence the states of M' are defined as subsets of Q. As M starts with
the initial state qo, q'o is defined as [qo]. A string w belongs to T(M) if a final
state is one of the possible states that M reaches on processing w. So, a final
state in M' (i.e. an element of F') is any subset of Q containing some final
state of M.
Now we can define 8':
(iv) 8'([qb q2. .... qi], a) = 8(q[, a) u 8(q2, a) u '" U 8(qi' a).
Equivalently.
if and only if
8({ql' ..., q;}, a) = {PI, P2 • ..., Pi}'
Before proving L = T(M'), we prove an auxiliary result
8'(q'o, x) = [qj, .. '. q;],
if and only if 8(qo, x) = {qj, "" q;} for all x in P.
We prove by induction on Ix I. the 'if part. i.e.
8'(q'o. x) = [qJ' q2. , ... q;]
if 8(qo. x) = {qJ ..... q;}.
(3.4)
(3.5)