Non-deterministic Finite Automata

Non-Deterministic Finite Automata

1

Nondeterministic Finite Automaton (NFA) Alphabet = {a}

a

q0

q1 a

q2

a

q3 2

Alphabet = {a} Two choices a

q0

q1 a

q2

a

q3 3

Alphabet = {a} Two choices a

q0

q1 a

q2

No transition

a

q3

No transition

4

First Choice a a

a

q0

q1 a

q2

a

q3 5

First Choice a a

a

q0

q1 a

q2

a

q3 6

First Choice a a

a

q0

q1 a

q2

a

q3 7

First Choice a a All input is consumed

a

q0

q1 a

q2

“accept”

a

q3 8

Second Choice a a

a

q0

q1 a

q2

a

q3 9

Second Choice a a

a

q0

q1 a

q2

a

q3 10

Second Choice a a

a

q0

q1 a

a

q3

q2

No transition: the automaton hangs 11

Second Choice a a Input cannot be consumed

a

q0

q1 a

q2

a

q3

“reject”

12

An NFA accepts a string: when there is a computation of the NFA that accepts the string

There is a computation: all the input is consumed and the automaton is in an accepting state 13

Example

aa

is accepted by the NFA: “accept” a

q0

q1

a

q2

a

q0

a

q3

because this computation accepts aa

q1 a

a

q3

q2

“reject”

14

Rejection example a

a

q0

q1 a

q2

a

q3 15

First Choice a

a

q0

q1 a

q2

a

q3 16

First Choice a “reject”

a

q0

q1 a

q2

a

q3 17

Second Choice a

a

q0

q1 a

q2

a

q3 18

Second Choice a

a

q0

q1 a

q2

a

q3 19

Second Choice a

a

q0

q1 a

q2

a

q3

“reject”

20

An NFA rejects a string: when there is no computation of the NFA that accepts the string.

For each computation: • All the input is consumed and the automaton is in a non final state

OR • The input cannot be consumed 21

Example

a

is rejected by the NFA: “reject” a

q0

q1 a

q2

a

q0

a

q3

“reject”

q1 a

q2

a

q3

All possible computations lead to rejection 22

Rejection example a a a

a

q0

q1 a

q2

a

q3 23

First Choice a a a

a

q0

q1 a

q2

a

q3 24

First Choice a a a

a

q0

q1 a

a

q3

q2 No transition: the automaton hangs

25

First Choice a a a Input cannot be consumed

a

q0

q1 a

q2

“reject”

a

q3 26

Second Choice a a a

a

q0

q1 a

q2

a

q3 27

Second Choice a a a

a

q0

q1 a

q2

a

q3 28

Second Choice a a a

a

q0

q1 a

a

q3

q2

No transition: the automaton hangs 29

Second Choice a a a Input cannot be consumed

a

q0

q1 a

q2

a

q3

“reject”

30

aaa

is rejected by the NFA: “reject” a

q0

q1

a

q2

a

q0

a

q3

q1 a

a

q3

q2

“reject”

All possible computations lead to rejection 31

Language accepted:

a

q0

q1 a

L = {aa} q2

a

q3 32

Lambda Transitions

q0 a

q1 λ

q2 a

q3

33

a a

q0 a

q1 λ

q2 a

q3

34

a a

q0 a

q1 λ

q2 a

q3

35

(read head does not move)

a a

q0 a

q1 λ

q2 a

q3

36

a a

q0 a

q1 λ

q2 a

q3

37

all input is consumed

a a

“accept”

q0 a String

aa

q1 λ

q2 a

q3

is accepted 38

Rejection Example

a a a

q0 a

q1 λ

q2 a

q3

39

a a a

q0 a

q1 λ

q2 a

q3

40

(read head doesn’t move)

a a a

q0 a

q1 λ

q2 a

q3

41

a a a

q0 a

q1 λ

q2 a

q3

No transition: the automaton hangs 42

Input cannot be consumed

a a a

“reject”

q0 a String

aaa

q1 λ

q2 a

q3

is rejected 43

Language accepted:

q0 a

q1 λ

L = {aa}

q2 a

q3

44

Another NFA Example

q0

a

b

q1

q2

λ

q3

λ 45

a b

q0

a

b

q1

q2

λ

q3

λ 46

a b

q0

a

b

q1

q2

λ

q3

λ 47

a b

q0

a

b

q1

q2

λ

q3

λ 48

a b

“accept”

q0

a

b

q1

q2

λ

q3

λ 49

Another String

a b a b

q0

a

b

q1

q2

λ

q3

λ 50

a b a b

q0

a

b

q1

q2

λ

q3

λ 51

a b a b

q0

a

b

q1

q2

λ

q3

λ 52

a b a b

q0

a

b

q1

q2

λ

q3

λ 53

a b a b

q0

a

b

q1

q2

λ

q3

λ 54

a b a b

q0

a

b

q1

q2

λ

q3

λ 55

a b a b

q0

a

b

q1

q2

λ

q3

λ 56

a b a b

“accept”

q0

a

b

q1

q2

λ

q3

λ 57

Language accepted

L = { ab, abab, ababab, ...} = { ab} q0

a

+

b

q1

q2

λ

q3

λ 58

Another NFA Example

0 q0

1

q1

0, 1 q2

λ 59

Language accepted

L(M ) = { λ, 10, 1010, 101010, ...} = { 10} *

0 q0

1

q1

λ

0, 1 q2

(redundant state)

60

Remarks: •The λ symbol never appears on the input tape •Simple automata:

M1 q0

M2

L(M1 ) = {}

L(M 2 ) = {λ}

q0

61

•NFAs are interesting because we can express languages easier than FAs NFA

q0

a

M1

q2

q1

a q0

L( M1 ) = {a}

a

M2

FA

a

q1

L( M 2 ) = {a} 62

Formal Definition of NFAs

M = ( Q, Σ, δ , q0 , F )

Q:

Set of states, i.e.

{ q0 , q1, q2 }

Σ:

Input aplhabet, i.e.

{ a, b}

δ:

Transition function

q0 : Initial state

F:

Accepting states 63

Transition Function δ

δ ( q0 , 1) = { q1} 0 q0

1

q1

0, 1 q 2

λ 64

δ (q1,0) = {q0 , q2 } 0 q0

1

q1

0, 1 q 2

λ 65

δ (q0 , λ ) = {q0 , q2 } 0 q0

1

q1

0, 1 q 2

λ 66

δ (q2 ,1) = ∅ 0 q0

1

q1

0, 1 q 2

λ 67

Extended Transition Function δ *

δ * ( q0 , a ) = { q1}

q5

q4 a q0

a

a b

q1

λ

q2

λ

q3 68

δ * ( q0 , aa ) = { q4 , q5 }

q5

q4 a q0

a

a b

q1

λ

q2

λ

q3 69

δ * ( q0 , ab ) = { q2 , q3 , q0 }

q5

q4 a q0

a

a b

q1

λ

q2

λ

q3 70

Formally

q j ∈ δ * ( qi , w) : there is a walk from qi to q j with label

w

w

qi

qj

w = σ 1σ 2 σ k

qi

σ1

σ2

σk

qj 71

The Language of an NFA M

F = { q0 ,q5 }

q5

q4 a q0

a

a b

q1

q2

λ

q3

λ

δ * ( q0 , aa ) = { q4 , q5 }

∈F

aa ∈ L(M ) 72

F = { q0 ,q5 }

q5

q4 a q0

a

a b

q1

q2

λ

q3

λ

δ * ( q0 , ab ) = { q2 , q3 , q0 }

∈F

ab ∈ L( M ) 73

F = { q0 ,q5 }

q5

q4 a q0

a

a b

q1

q2

λ

q3

λ

δ * ( q0 , abaa ) = { q4 , q5 }

∈F

aaba ∈ L(M ) 74

F = { q0 ,q5 }

q5

q4 a q0

a

a b

q1

q2

λ

q3

λ

δ * ( q0 , aba ) = { q1}

∉F

aba ∉ L( M ) 75

q5

q4 a q0

a

a b

q1

q2

λ

q3

λ

L( M ) = { λ } ∪ { ab} * {aa} 76

Formally The language accepted by NFA

M

is:

L( M ) = { w1, w2 , w3 ,...}

where

δ * (q0 , wm ) = {qi , q j ,..., qk ,}

and there is some

qk ∈ F (accepting state) 77

w∈ L( M )

δ * (q0 , w) qi

w q0

qk

w w

qk ∈ F

qj

78