3.1 Automata

Automata Theory

Part 1:

Introduction & NFA November 2002

Introduction  an abstract machine  a specification with many possible implementations  issues of functionality (power) and efficiency  hierarchy of automata corresponds to hierarchy of

grammars

 languages generated by grammars are accepted by

automata

 the computational tasks performed by an automaton are

very closely related to the structures & meanings modelled by the corresponding grammar. 2

Computing power of automata:  the simplest automata are only capable of adding numbers

and recognising simple expressions

 more complex automata can evaluate arbitrary expressions

and compile computer programs

 the most powerful automata can perform any computable

task - significantly, there are tasks which cannot be computed.

 automata theory also reveals limitations on what can be

made efficient.

3

Deterministic Finite Automaton ­ DFA  The simplest automata - main features: • finite number of states • state changes in response to an input symbol • no choice of move

DFA = (Q,T,F,g) where Q = set of states, including initial state T = set of input symbols F = set of final states, F ⊆ Q g = transition function, Q × T→ Q mapping 4

DFA Transition or move defined by, • g(q,a) = q’ where q,q’ ∈ Q, a∈T q

a

q’

5

DFA  Operation can be represented as a state diagram in which:

- nodes represent states, - arcs represent transitions or moves, - the initial state is arrowed, - and the final states are represented as squares.

q Initial state

a1

q’

a2

intermediate state

f final state

f∈F 6

DFA  State of a DFA changes predictably in response to

an input symbol - so at any time the entire future behaviour of a DFA is fully determined by • 1. the current state, q • 2. the remaining input symbols, x

 Combine these into a pair (q, x) giving a

complete description of current situation.

7

Teletext remote control example text

tv tv

digit1

tv

d

text

tv d

digit2

new page

tv

d

 d

=  0 …  9

wait

 d

• Pressing the text button followed by three digits causes the appropriate page to be loaded and displayed. • Pressing the tv button causes a return to the normal image.

8

DFA ­ State Transition  A move can be defined either in terms of the transition function:

g(q,a) = q’

 or, equivalently in terms of how the complete description evolves:

(q,ax) ⇒ (q’,x)

 Note the state change to q’ and the fact that the input symbol a is

read and then dropped.

 A sequence of moves between these complete descriptions is denoted

by ⇒*

 An input string w ∈ T* is accepted by the automaton if there is a finite

sequence of moves such that (q0,w) ⇒* (q’,λ) for some q’ ∈ F , i.e. the automaton is in a final state when the input string is exhausted (λ).

 The language L(A) defined by an automaton A is the set of strings

accepted by it, (a similar concept to the language generated by a grammar).

9

Parity tester example  Q = {q0,q1}, F={q1}, T={0,1}

where q0, q1 represent odd and even parity states respectively (binary input). Transition function is defined as follows: Odd­parity tester

• g(q0,0) = q0 0

• g(q0,1) = q1 • g(q1,0) = q1 • g(q1,1) = q0

0

1

q0

q1 1

10

Binary adder DFA example  Note that a DFA halts when its input string is exhausted (or

when no move is possible for a given (state, input) pair), and not just because it has entered a final state. Some machines can also generate an output for every move. Let the output vocabulary be T*. (0,0)→0

(1,1)→1 (1,1)→ 0

q0

q1 (0,0)→ 1

(0,1)→1 (1,0)→1

(0,1)→0 (1,0)→0

T = { ( 0 ,0), ( 0,1), (1,0), (1,1) }, T ′ = {0 ,1}

input: input:

0 0

1 0

1 1

0 0

1 0

0 1

1 1

state: q 0 q1 q 1 q0 q 1 q1 q1 q 0 output: 1 0 0 1 0 0 0

The state diagram shows the output to the right of each arrow.

11

Binary Multiply by 3 0 →0

1→1 1→1

q0

1→0 q1

0→1 carry 0

T = T ′ = {0 ,1}

q2 0→0

carry 1

carry 2

input: state:

0 0 1 1 0 q 0 q1 q 2 q1 q 0 q0

output: 1

0

0

1

0

In general, a DFA to multiply by n will require n states. No DFA can multiply an arbitrary pair of numbers. 12

Non­deterministic Finite Automaton ­ NFA  Finite automaton with a choice of moves: there may be

more than one possible move for a given (state,input) pair.  The transition function is many-valued:

g(q,a) ⊆ Q

for q ∈ Q, q ∈ T

 The machine “chooses” a move from the set of

possibilities, either at random or else by some mysterious unexplained process.  Non-deterministic automata are not really practical

machines, but they have great theoretical importance, and lead to some useful general ideas and procedures. 13

NFA

 Does this non-determinism increase the computing power

of the machine? The answer for a finite automaton is no:

 Given any NFA it is always possible to construct an

equivalent DFA. Equivalent here means that the machines accept the same strings, and generate the same output (if any).

14

NFA  If the set of states of the NFA is Q, then the states of the

DFA are subsets of Q, with initial state {q0}. Extend the transition function to subsets of Q by defining, G(R,a) =

∪ g(q,a)

for R ⊆ Q, a ∈ T

q∈R

 Thus, make transition unique by forming the union of all the

possibilities in order to construct a new set (state) to go to in response to an input symbol.

15

NFA to DFA conversion  The non-determinism in the arcs in the original machine is

embedded within the states of the new machine. We construct the states of the DFA recursively.

 First define states Ra = G({q0},a) = g(q0,a) for all a, then

more new states Rab = G(Ra,b) for all a,b, and so on until no new states are generated.

 The final states of the DFA are those states R for which

R∩F≠∅

16

NFA to DFA conversion  Example:

R0

b q0 b q3 NFA

a a

q1 a q2

{q0}

b a

b

a

a

q4 {q3} R2 DFA

R5

R3

a

b {q2}

b

R4

b a

{q1, q2}

b

b a

R1

{q1,q4} b

{q4} a

b a

R6

{q1}

17

18