Non Deterministic Automata

1
Non Deterministic Automata

2
1
q
2
q
3
q
a
a
a
0
q
} {a Alphabet =
Nondeterministic Finite Accepter (NFA)
3
1
q
2
q
3
q
a
a
a
0
q
Two choices
} {a Alphabet =
4
No transition
1
q
2
q
3
q
a
a
a
0
q
Two choices
No transition
} {a Alphabet =
5
a a
0
q
1
q
2
q
3
q
a
a
First Choice
a
6
a a
0
q
1
q
2
q
3
q
a
a
a
First Choice
7
a a
0
q
1
q
2
q
3
q
a
a
First Choice
a
8
a a
0
q
1
q
2
q
3
q
a
a
a
accept
First Choice
9
a a
0
q
1
q
2
q
3
q
a
a
Second Choice
a
10
a a
0
q
1
q
2
q
a
a
Second Choice
a
3
q
11
a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
No transition:
the automaton hangs
12
a a
0
q
1
q
2
q
a
a
a
3
q
Second Choice
reject
13
Observation
An NFA accepts a string
if
there is a computation of the NFA
that accepts the string
14
Example
aa is accepted by the NFA:
0
q
1
q
2
q
3
q
a
a
a
15
Lambda Transitions
1
q
3
q
a
0
q

1
q
a
16
a a
1
q
3
q
a
0
q

2
q
a
17
a a
1
q
3
q
a
0
q

2
q
a
18
a a
1
q
3
q
a
0
q

2
q
a
(read head doesnt move)
19
a a
1
q
3
q
a
0
q

2
q
a
20
a a
1
q
3
q
a
0
q

2
q
a
accept
String is accepted
aa
21
Language accepted:
} {aa L =
1
q
3
q
a
0
q

2
q
a
22
Another NFA Example
0
q
1
q
2
q
a
b
3
q
23
a
b
0
q
1
q
2
q
a
b
3
q
24
0
q
2
q
a
b
3
q
a
b
1
q
25
a
b
0
q
1
q
a
b
3
q
2
q
26
a
b
0
q
1
q
a
b
3
q
2
q
accept
27
0
q
a
b
a
b
Another String
a
b
1
q
2
q
3
q
28
0
q
a
b
a
b
a
b
1
q
2
q
3
q
29
0
q
a
b
a
b
a
b
1
q
2
q
3
q
30
0
q
a
b
a
b
a
b
1
q
2
q
3
q
31
0
q
a
b
a
b
a
b
1
q
2
q
3
q
32
0
q
a
b
a
b
a
b
1
q
2
q
3
q
33
0
q
a
b
a
b
a
b
1
q
2
q
3
q
34
a
b
a
b
0
q
a
b
1
q
2
q
3
q
accept
35
{ }
{ }
+
=
=
ab
ababab abab ab L ... , , ,
Language accepted
0
q
1
q
2
q
a
b
3
q
36
Another NFA Example

0
q
1
q
2
q
0
1
1 , 0
37
{ }
{ }* 10
... , 101010 , 1010 , 10 ,
=
= L
0
q
1
q
2
q
0
1
1 , 0
Language accepted
38
Formal Definition of NFAs

( ) F q Q M , , , ,
0
o E =
: Q
: o
:
0
q
: F
Set of states, i.e.
{ }
2 1 0
, , q q q
: E
Input aplhabet, i.e. { } b a,
Transition function
Initial state
Final states
39
( ) { }
1 0
1 , q q = o
0
1
1 , 0
Transition Function
0
q
1
q
2
q
o
40
0
q
0
1
1 , 0
} , { ) 0 , (
2 0 1
q q q = o
1
q
2
q
41
0
q
0
1
1 , 0
1
q
2
q
} , { ) , (
2 0 0
q q q = o
42
0
q
0
1
1 , 0
1
q
2
q
C = ) 1 , (
2
q o
43
Extended Transition Function

* o
0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
1 0
, * q a q = o
44
( ) { }
5 4 0
, , * q q aa q = o
0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
45
( ) { }
0 3 2 0
, , , * q q q ab q = o
0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
46
Formally

( ) w q q
i j
, * o e It holds
if and only if
there is a walk from to
with label

i
q
j
q
w
47
The Language of an NFA

0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
5 4 0
, , * q q aa q = o
M
) (M L aae
{ }
5 0
, q q F =
48

0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { }
0 3 2 0
, , , * q q q ab q = o ( ) M L abe
{ }
5 0
, q q F =
49

0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
{ }
5 0
, q q F =
( ) { }
5 4 0
, , * q q abaa q = o
) (M L aabae
50

0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
{ }
5 0
, q q F =
( ) { }
1 0
, * q aba q = o
( ) M L abae
51

0
q
5
q
4
q
3
q
2
q
1
q
a
a a
b
( ) { } { } { } { } aa ab ab aa M L
+
= *
52
Formally
The language accepted by NFA is:

where

and there is some
M
( ) { } ,... , ,
3 2 1
w w w M L =
,...} , { ) , ( *
0 j i m
q q w q = o
F q
k
e (final state)
53

0
q
k
q
w
w
w
) , ( *
0
w q o ( ) M L we
F q
k
e
i
q
j
q
54
Equivalence of NFAs and DFAs

55
Equivalence of Machines

For DFAs or NFAs:

Machine is equivalent to machine

if

1
M
2
M
( ) ( )
2 1
M L M L =
56
Example

0
q
1
q
2
q
0
1
1 , 0
0
q
1
q
2
q
0
1
1
0
1 , 0
NFA
DFA
( ) * } 10 {
1
= M L
( ) * } 10 {
2
= M L
1
M
2
M
57
Since

machines and are equivalent
( ) ( ) { }* 10
2 1
= = M L M L
1
M
2
M
0
q
1
q
2
q
0
1
1 , 0
0
q
1
q
2
q
0
1
1
0
1 , 0
DFA
NFA
1
M
2
M
58
Question: NFAs = DFAs ?
Same power?
Accept the same languages?
59
Question: NFAs = DFAs ?
Same power?
Accept the same languages?
YES!
60
We will prove:
Languages
accepted
by NFAs
Languages
accepted
by DFAs
=
61
We will prove:
Languages
accepted
by NFAs
Languages
accepted
by DFAs
=
NFAs and DFAs have the same
computation power
62
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 1
63
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 1
Proof:
Every DFA is also an NFA
64
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 1
Proof:
Every DFA is also an NFA
A language accepted by a DFA
is also accepted by an NFA
65
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 2
66
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 2
Proof:
Any NFA can be converted to an
equivalent DFA
67
Languages
accepted
by NFAs
Languages
accepted
by DFAs
_
Step 2
Proof:
Any NFA can be converted to an
equivalent DFA
A language accepted by an NFA
is also accepted by a DFA
68
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
69
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
70
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
71
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
72
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
73
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
74
NFA to DFA

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
75
NFA to DFA: Remarks

We are given an NFA

We want to convert it
to an equivalent DFA

With
M
M
'
( ) ) (M L M L
'
=
76
If the NFA has states

the DFA has states in the powerset

,... , ,
2 1 0
q q q
{ } { } { } { },.... , , , , , , ,
7 4 3 2 1 1 0
q q q q q q q C
77
Procedure NFA to DFA

1. Initial state of NFA:

Initial state of DFA:
0
q
{ }
0
q
78
Example

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
79
2. For every DFAs state

Compute in the NFA

Add transition

} ,..., , {
m j i
q q q
( )
( )
...
, , *
, , *
a q
a q
j
i
o
o
} ,..., , {
m j i
q q q
' ' '
( ) } ,..., , { }, ,..., , {
m j i m j i
q q q a q q q
' ' '
= o
=
80
Exampe

a
b
a
0
q
1
q
2
q
NFA
{ }
0
q
{ }
2 1
, q q
a
DFA
} , { ) , ( *
2 1 0
q q a q = o
{ } ( ) { }
2 1 0
, , q q a q = o
81

Repeat Step 2 for all letters in alphabet,
until
no more transitions can be added.
82
Example

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
83
3. For any DFA state

If some is a final state in the NFA

Then,
is a final state in the DFA

} ,..., , {
m j i
q q q
j
q
} ,..., , {
m j i
q q q
84
Example

a
b
a
0
q
1
q
2
q
NFA
DFA
{ }
0
q
{ }
2 1
, q q
a
C
b
a
b
b a,
F q e
1
{ } F q q
'
e
2 1
,
85
Theorem

Take NFA
M
Apply procedure to obtain DFA M
'
Then and are equivalent :
M
M
'
( ) ( ) M L M L
'
=
86
Finally
We have proven
Languages
accepted
by NFAs
Languages
accepted
by DFAs
=
87
Languages
accepted
by NFAs
Languages
accepted
by DFAs
=
We have proven
Regular Languages
88
Languages
accepted
by NFAs
Languages
accepted
by DFAs
=
We have proven
Regular Languages
Regular Languages

Non Deterministic Automata

Uploaded by

Copyright:

Available Formats

Non Deterministic Automata

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Non Deterministic Automata

Uploaded by

Copyright:

Available Formats

1

Non Deterministic Automata

You might also like