NFAs accept the Regular
Languages
Prof. Busch - LSU
1
Equivalence of Machines
Definition:
Machine
if
M1
is equivalent to machine
M2
LM1   LM 2 
Prof. Busch - LSU
2
Example of equivalent machines
NFA
LM1   {10}*
0
q0
q1
1
DFA
LM 2   {10}*
M1
M2
0,1
0
q0
1
q1
1
q2
0
Prof. Busch - LSU
3
Theorem:
Languages
accepted
by NFAs

Regular
Languages
Languages
accepted
by DFAs
NFAs and DFAs have the same computation power,
accept the same set of languages
Prof. Busch - LSU
4
Proof:
we only need to show
Languages
accepted
by NFAs

Regular
Languages
AND
Languages
accepted
by NFAs

Prof. Busch - LSU
Regular
Languages
5
Proof-Step 1
Languages
accepted
by NFAs

Regular
Languages
Every DFA is trivially an NFA
Any language L accepted by a DFA
is also accepted by an NFA
Prof. Busch - LSU
6
Proof-Step 2
Languages
accepted
by NFAs

Regular
Languages
Any NFA can be converted to an
equivalent DFA
Any language L accepted by an NFA
is also accepted by a DFA
Prof. Busch - LSU
7
Conversion NFA to DFA
a
NFA M
a
 q
q
q
0
1
2
b
DFA
M
q0 
Prof. Busch - LSU
8
NFA
 * (q0, a )  {q1, q2 }
a
M
q0
a

q1
q2
b
DFA
M
q0 
a
q1, q2 
Prof. Busch - LSU
9
NFA
 * (q0 , b )  
a
M
q0
a
empty set

q1
q2
b
DFA
M
q0 
a
q1, q2 

trap state
b
Prof. Busch - LSU
10
 (q1, a )  {q1, q2 }
 * (q2, a )  
*
NFA
a
M
q0
a

q1
union
q2
q1, q2 
b
DFA
a
M
q0 
a
q1, q2 
b

Prof. Busch - LSU
11
 (q1, b )  {q0 }
 * (q2, b )  {q0 }
*
NFA
a
M
q0
a

q1
union
q2
q0 
b
DFA
M
a
b
q0 
a
q1, q2 
b

Prof. Busch - LSU
12
NFA
a
M
q0
a

q1
q2
b
DFA
M
a
b
q0 
a
q1, q2 
b

Prof. Busch - LSU
a, b trap state
13
END OF CONSTRUCTION
NFA
a
M
q0
a

q1
q1  F
q2
b
DFA
M
a
b
q0 
a
q1, q2 
b

Prof. Busch - LSU
q1, q2  F 
a, b
14
General Conversion Procedure
Input: an NFA
M
Output: an equivalent DFA M 
with LM   L(M )
Prof. Busch - LSU
15
The NFA has states
q0 , q1, q2 ,...
The DFA has states from the power set
, q0 , q1 , q0 , q1 , q1, q2, q3, ....
Prof. Busch - LSU
16
Conversion Procedure Steps
step
1.
Initial state of NFA:
q0
 q0,    q0,
*
Initial state of DFA: q0 , 
Prof. Busch - LSU
17
Example
NFA
 * q0 ,    q0 
a
M
q0
a

q1
q2
b
DFA
M
q0 
Prof. Busch - LSU
18
step
2. For every DFA’s state {qi , q j ,..., qm}
compute in the NFA
 * qi , a 
  * q j , a 
...
Union
 {qk , ql,...,qn }
  * qm , a 
add transition to DFA
 {qi , qj ,...,qm }, a   {qk , ql,...,qn }
Prof. Busch - LSU
19
 * (q0 , a)  {q1, q2}
Example
NFA
a
M
a
q0

q1
q2
b
DFA
M
q0 
a
q1, q2 
 q0 , a   q1, q2 
Prof. Busch - LSU
20
step
3. Repeat Step 2 for every state in DFA and
symbols in alphabet until no more states
can be added in the DFA
Prof. Busch - LSU
21
Example
NFA
a
M
q0
a

q1
q2
b
DFA
M
a
b
q0 
a
q1, q2 
b

Prof. Busch - LSU
a, b
22
step
4. For any DFA state {qi , q j ,..., qm}
if some
q j is accepting state in NFA
Then, {qi , q j ,..., qm }
is accepting state in DFA
Prof. Busch - LSU
23
Example
NFA
a
M
q0
a

q1
q1  F
q2
b
DFA
M
a
b
q0 
a
q1, q2 
b

Prof. Busch - LSU
q1, q2  F 
a, b
24
Lemma:
If we convert NFA M to DFA M 
then the two automata are equivalent:
L  M   L M  
Proof:
We only need to show:
LM   LM 
AND
LM   LM 
Prof. Busch - LSU
25
First we show:
LM   LM 
We only need to prove:
w L(M )
w  L(M )
Prof. Busch - LSU
26
NFA
Consider
w L(M )
w
q0
qf
symbols
w  1 2  k
q0
1
2
Prof. Busch - LSU
k
qf
27
symbol
qi
i
qj
denotes a possible sub-path like
qi


symbol
i
Prof. Busch - LSU

qj
28
We will show that if
w L(M )
w  1 2  k
NFA
M:
q0
1
k
2
qf
then
DFA
1
M:
{q0 ,}
state
label
2
w  L(M )
Prof. Busch - LSU
k
{q f ,}
state
label
29
More generally, we will show that if in
(arbitrary string)
NFA
M:
q0
M:
v  a1a2 an
a1
qi
a2
qj
ql
an
qm
then
DFA
M:
a1
{q0 ,}
a2
{qi ,} {q j ,}
Prof. Busch - LSU
an
{ql ,} {qm ,}
30
Proof by induction on
v  a1
Induction Basis: |v | 1
NFA
M:
DFA
M:
q0
|v|
a1
qi
a1
{q0 ,}
{qi ,}
is true by construction of M 
Prof. Busch - LSU
31
Induction hypothesis:
1 | v | k
v  a1a2 ak
Suppose that the following hold
NFA
M:
DFA
M:
a1
q0
a1
{q0 ,}
qi
a2
qj
a2
{qi ,} {q j ,}
Prof. Busch - LSU
qc
ak
qd
ak
{qc ,} {qd ,}
32
| v | k  1
v  a1a2 ak ak 1  vak 1


Induction Step:
v
Then this is true by construction of M 
NFA
M:
q0
a1
qi
a2
qj
qc
ak
qd
ak 1
qe
v
DFA
M:
a1
{q0 ,}
ak
a2
{qi ,} {q j ,}
v
Prof. Busch - LSU
ak 1
{qc ,} {qd ,}
{qe ,}
33
Therefore if
w L(M )
w  1 2  k
NFA
M:
q0
1
k
2
qf
then
DFA
M:
1
{q0 ,}
2
w  L(M )
Prof. Busch - LSU
k
{q f ,}
34
We have shown:
With a similar proof
we can show:
Therefore:
LM   LM 
LM   LM 
LM   LM 
END OF LEMMA PROOF
Prof. Busch - LSU
35
Descargar

Languages and Finite Automata