Finite Automata

This ppt is the work by Dr. Costas Busch, used with permission, and available from http://csc.lsu.edu/~busch/courses/theorycomp/fall2008/ 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

All input is consumed a q0

q1

a

q2

“accept”

a

q3

7

Second Choice a a

a

q0

q1

a

q2

a

q3

8

Second Choice a a

Input cannot be consumed a q0

a

q1

a

q2

Automaton Halts

q3

“reject”

9

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

i.e., all the input string is processed and the automaton is in an accepting state

10

aa

is accepted by the NFA:

“accept”

a

q0

q1

a

q2

a

q0

a

q3

because this computation accepts aa

q1

a

q2

a

q3

“reject”

this computation is ignored

11

Rejection example a a

q0

q1

a

q2

a

q3

12

First Choice a “reject” a q0

q1

a

q2

a

q3

13

Second Choice a a

q0

q1

a

q2

a

q3

14

Second Choice a a

q0

q1

a

q3

“reject”

q2

a

15

Another Rejection example a a a

a

q0

q1

a

q2

a

q3

16

First Choice a a a

a

q0

q1

a

q2

a

q3

17

First Choice a a a

Input cannot be consumed a q0

q1

a

q3

a

q2

“reject”

Automaton halts

18

Second Choice a a a

a

q0

q1

a

q2

a

q3

19

Second Choice a a a

Input cannot be consumed a q0

q1

a

q2

Automaton halts

a

q3

“reject”

20

An NFA rejects a string: if 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

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

aaa is rejected by the NFA:

“reject”

a

q0

q1

a

q2

a

q0

a

q3

q1

a

q2

a

q3

“reject”

All possible computations lead to rejection

23

Language accepted:L {aa}

a

q0

q1

a

q2

a

q3

24

Epsilon Transitions

q0

a

q1

q2

a

q3

25

a a

q0

a

q1

q2

a

q3

26

a a

q0

a

q1

q2

a

q3

27

input tape head does not move a a

q0

a

q1

q2

a

q3

28

all input is consumed a a

“accept”

q0

String

aa

a

q1

q2

a

q3

is accepted

29

Rejection Example a a a

q0

a

q1

q2

a

q3

30

a a a

q0

a

q1

q2

a

q3

31

(read head doesn’t move) a a a

q0

a

q1

q2

a

q3

32

Input cannot be consumed a a a

Automaton halts

“reject”

q0

String

a

aaa

q1

q2

a

q3

is rejected

33

Language accepted:L {aa}

q0

a

q1

q2

a

q3

34

Another NFA Example

q0

a

b

q1

q2

q3

35

a b

q0

a

b

q1

q2

q3

36

a b

q0

a

q1

b

q2

q3

37

a b

“accept”

q0

a

q1

b

q2

q3

38

Another String

a b a b

q0

a

q1

b

q2

q3

39

a b a b

q0

a

q1

b

q2

q3

40

a b a b

q0

a

q1

b

q2

q3

41

a b a b

q0

a

q1

b

q2

q3

42

a b a b

q0

a

q1

b

q2

q3

43

a b a b

q0

a

q1

b

q2

q3

44

a b a b

“accept”

q0

a

q1

b

q2

q3

45

Language accepted

L ab, abab, ababab, ...

ab q0 a

q1

b

q2

q3

46

Another NFA Example

0 q0 1

q1

0, 1 q2

47

Language accepted

L( M ) , 10, 1010, 101010, ...

10 *

0

q0

1

q1

0, 1 q2

(redundant state) 48

Remarks:

•The symbol never appears on the input tape

•Simple automata:

M1 q0 M2

L(M1 ) = {}

L( M 2 ) { }

q0

49

•NFAs are interesting because we can express languages easier than DFAs

NFA

q0

a

M1

DFA

q2

q1

a q0 L( M1 ) = {a}

a

M2

a

q1

L( M 2 ) = {a}

50

Formal Definition of NFAs

M Q, , , q0 , F

q0 , q1, q2

Q:

Set of states, i.e.

:

Input aplhabet, i.e. a, b

:

Transition function

q0 : Initial state

F:

Accepting…