Ch2 finite automaton

finite automata

1. Chapter two

FINITE AUTOMATA



Chapter programme
FA
DFA
NFA
-NFA
FA equivalence
FA minimization

2. What is a finite automaton?
An automaton with a finite number of states is called a Finite Automaton FA or
Finite State Machine FSM.
FSM is to correlate with Turing machines.
FSA is a virtual device for manipulating stings, one character at a time.
The machine determines whether that string is in the language or not.
An automaton whose output response is limited to yes or no is an acceptor
Accepts input string and either accepts or rejects it
Measures of complexity
Running time
Amount of memory used

2

3. Conti…
A device consists of
An Input tape,
a tape reading device, and
a finite control unit.
Uses a limited, constant amount of memory
Easy to model
Limited application
it is a very simple model of a computer
3

4. Conti…







Finite automaton
4

5. Conti …

Input tap

finite control

0 1 1
0
q
•Read the current letter of input under the tape head.
•Transit to a new state depending on the current input and the
current state, as dictated by the transition function.
•Halt after consuming the entire input.
5

6. Conti…
The machine satisfies the following conditions:
The tape has the left end and extends to the right without
an end.
The tape is divide into squares in each of which a symbol
can be written prior to the start of the operation of the
automaton.
The tape has a read only head.
The head is always at the leftmost square at the beginning of
the operation.

6

7. Conti…

The head moves to the right one square every time it
reads a symbol. It never moves to the left. When it sees no
symbol, it stops and the automaton terminates its
operation.
There is a finite control which determines the state of the
automaton and also controls the movement of the head

7

8. Operation of finite automata
The machine reads an input tape (string of symbols)
The machine can be in any number of states
As each symbol is read (from left to right), the machine switches from
state to state based on what symbol is read(from the string w) at each point.
After having read the entire string w, if the machine ends up in one of a set
of final states, the string is accepted, unless rejected-not accepted.
8

9. Conti…

Like grammars, finite state automata define languages.
Different components of automata
Input: are strings
States( including start and final):Indicates the status of
the machine after consuming some portion of the input.
Transition Function: maps state/input pair to states
Arcs: labeled with symbol that triggers the transition

9

10. Conti …
FA execution: On an input sequence
Begin in the start state
If the next input char matches the label on a transition from the current state to a new
state, go to that new state
Continue making transitions on each input char
•If no move is possible, then stop
•If in accepting state, then
accept
Representation of finite automata
For a finite automata M, represent in one of the following five ways:
Formal description of M,
Simply list its rules together with specifying the start state and final state of M,
By state table,
State diagram, and
Informal description.
10

11. example
Before we give a formal definition of a finite automaton, we
consider an example in which such an automaton shows up in a natural
way.
consider the problem of designing a “computer” that controls a toll
gate.
Read the problem carefully and understood the following
paragraph:
11

12. Cont..
When a car arrives at the toll gate, the gate is closed. The gate
opens as soon as the driver has payed 25 cents. We assume
that we have only three coin denominations: 5, 10, and 25
cents. We also assume that no excess change is returned. After
having arrived at the toll gate, the driver inserts a sequence of
coins into the machine. At any moment, the machine has to
decide whether or not to open the gate, i.e., whether or not the
driver has paid 25 cents (or more). In order to decide this, the
machine is in one of the following six states, at any moment
during the process:

12

13. Conti…
The machine is in state q0, if it has not collected any money
yet.
The machine is in state q1, if it has collected exactly 5 cents.
The machine is in state q2, if it has collected exactly 10 cents
The machine is in state q3, if it has collected exactly 15 cents.
The machine is in state q4, if it has collected exactly 20 cents.
The machine is in state q5, if it has collected 25 cents or more.

13

14. Cont…
 Initially (when a car arrives at the toll gate), the machine is in
state q0. Assume, for example, that the driver presents the
sequence (10,5,5,10) of coins.
After receiving the first 10 cents coin, the machine switches from
state q0 to state q2.
After receiving the first 5 cents coin, the machine switches from
state q2 to state q3.
After receiving the second 5 cents coin, the machine switches from
state q3 to state q4.
After receiving the second 10 cents coin, the machine switches from
state q4 to state q5. At this moment, the gate opens. (Remember that
no change is given.)

14

15. Conti..
The “computer” that we designed in the toll gate example is a finite automaton with
set of states

An alphabet for inputs

Start state

Final state
25} 10, {5, = 
 
54321
,,,,, qqqqqqQ
o

 
0
q

5
qF
15

16. Toll gate designing
16

17. finite automata types
Deterministic finite automat: DFA
Non-deterministic finite automata: non-deterministic FA, NFA
for each input symbol, one can determine the state to which the machine will
move. Hence, it is called Deterministic Automaton. As it has a finite number of
states, the machine is called Deterministic Finite Machine or Deterministic
Finite Automaton.
17

18. DFA
On each input there is one and only
one state to which the automaton can
transition from its current state
One-way, infinite tape, broken into
cells
One-way, read-only tape head.
Finite control, i.e.,
finite number of states, and
transition rules between
them, i.e.,
a program, containing the
position of the read head,
current symbol being
scanned, and the current
“state.”
A string is placed on the tape, read
head is positioned at the left end, and
the DFA will read the string one
symbol at a time until all symbols have
been read. The DFA will then either accept or reject the string.
Deterministic finite automata – each
move is uniquely determined by the
current configuration
Single path
18

19. DFA– Formal Definition/description
A DFA is a 5-tupple

where:

is a finite set called the states
is a finite set called the alphabet
is the transition function
:is the start state, and
:is the set of accept states

  FqQ ,,,,
0


QQ:
Qq
0
QF
Q
19

20. DFA-state diagram
Represented by digraphs called state diagram: used to graphically represent
finite state machines to give an abstract description of the behavior of a
system.
State diagram is a type of diagram used in computer science and related fields
to describe the behavior of systems.






Start
state
state
Final
state
Path
20

21. Cont…
It has the following components:
The vertices represent the states.
The arcs labeled with an input alphabet show the transitions.
The initial state is denoted by an empty single incoming arc.
The final state is indicated by double circles.
Conventions in state diagram


0
q
Fsymbol
stransition
stateinitail state final
21

22. Transition diagram and tables
Transition diagrams
Each state is a node
For each state q ∈ Q and each symbol
a ∈ , let /(q, a) = p
Then the transition diagram has an
arc from q to p, labeled a
There is an arrow to the start state q0
Nodes corresponding to final states
are marked with doubled circle


Transition tables
Tabular representation of a function
The rows correspond to the states and
the columns to the inputs
The entry for the row corresponding
to state q and the column
corresponding to input a is the state
/(q, a)
The initial and final states are
denoted by → and * respectively.

22

23. Transition and extended transition
function for DFA
Transition function /: (Q x Σ)Q,
/ is defined for any q in Q and a in Σ, and /(q , a) = q’ is equal to some state q’ in Q,
could be q’=q
Intuitively, /(q, a) is the state entered by ε after reading symbol a while in state q.
If / is our transition function, then the extended transition function is denoted by /ˆ
The extended transition function is a function that takes a state q and a string w
and returns a state p (the state that the automaton reaches when starting in state q
and processing the sequence of inputs w )
/^(q , w) – The state entered after reading string w having started in state q
Extended transition function w
^
: ~Q x Σ
*
)  Q
Describes what happens when we start in any state and follow any sequence of
inputs

23

24. Cont …
Formally:
1) /
^
(q, 0) = q, If we are in a state q and read no inputs, then we are still in state q
and
2) For all w in Σ
*
and a in Σ: /
^
(q , wa) = / (/
^
(q , w), a) i.e. Recursive definition
Suppose w is a string of the form xa; that is a is the last symbol of w, and x is the
string consisting of all but the last symbol Then: /ˆ(q, w) =/(/ˆ(q, x), a)
To compute /ˆ(q, w), first compute(q, x), the state that the automaton is in after
processing all but the last symbol of w
Suppose this state is p, i.e. /ˆ(q, x) =p
Then /ˆ(q, w )is what we get by making a transition from state P on input a – the last
symbol of w.

24

25. Extension of / to Strings
Example #1:


What is /^(q0, 011)? Informally, it is the state entered by ε after
processing 011 having started in state q0.
Formally:
/^(q0, 011) = / (/^(q0,01), 1)
= w ~w ~ w
^
(q
0,0), 1), 1)
= w ~w ~w ~w
^
(q
0, ), 0), 1), 1)
= w ~w ~w~?
0,0), 1), 1)
= w ~w ~?
1, 1), 1)
= w ~?
1, 1)
= q
1
Is 011 accepted? No, since /^(q0, 011) = q1 is not a final state.

q
0
q
1
0
0
1
1
25

26. Conti …
Example #2:


What is /(q0, 011)? Informally, it is the state entered by ε after processing 011
having started in state q0.
Formally:
/(q0, 011) = / (/(q0,01), 1)
= w ~w ~w~?
0,0), 1), 1)
= w ~w ~?
1, 1), 1)
= w ~?
1, 1)
= q
1
Is 011 accepted? No, since /(q0, 011) = q1 is not a final state.
Language?

q
1
q
0
q
2
1 1
0
0
1
0
26

27. The language of a DFA
Given an automaton A = (Q,,,q0,F), and a string w  *:
w is accepted by A if the configuration (q0,w) yields the configuration (F, ), where
F is an accepting state.(A string is rejected if there exist NO path to any state in F
The language accepted by A, written L(A), is defined by: L(A) = {w  * : w is
accepted by A}
The language of a DFA A =(Q,Σ, /, q0, F), denoted δ(A) is defined by δ (A) = { w |
/ˆ(q0, w) is in F}
The language of A is the set of strings w that take the start state q0 to one of the
accepting states
A language is called a regular language if some finite automaton recognizes it.

27

28. Example 1, M1
M1 accepts the language of strings that end in aa.
State (transition) diagram






Write the language recognized by M1 formally?
What is the set of strings accepted by M1?
write the transition(state) table for m1?


1q
b
b
aa
0
q
2q
a
b
28

29. Conti ..
Description for M1








 
2,1,
qqqQ
o

ba,
1q
2q
2q
2q
0
q
0
q
0
q
0
q
1q
ab

29

30. Example 2, M2
FA accepts strings ending with b and not containing aa.
state diagram















What is the language recognized by M2?
List accepted and rejected strings by M2?
2q
b
a a
ba
ba,
b
0
q
3
q
1q
30

31. Example 3,M3






•M3= ~Q, Σ, w, ??, F o? M3
= ({q1, q2,q3}, {0,1}, w, q1, {q2})
•Accepted Strings or Words (w):
–?, ??, ??, ???, ???, ????, ????, ??????, …
If A is the set of all strings that machine M
accepts, we say:
•A is the language of machine M
1 and write L(M
3) = A
•M3
recognizes A or that M3
accepts A
•A = {?, ??, ??, ???, ???, ????, ????, ??????, …} o?
•A = {w| w contains at least one 1 and an even number of 0s follow the last 1}

31

32. δet Σ = {0, 1}. Give DFAs for {}, {0}, Σ
*
, and Σ
+
.

For {}: For {0}:






For Σ
*
: For Σ
+
:
0/1
q
0
0/1
q
0
q
1 q
0
0/1
0/1
0/
1
q
0 q
1
0/1
32

33. Non-deterministic finite automaton
Nondeterministic automata –
An automaton can be in several states at once
Can’t determine next move accurately
May have multiple next moves or paths
More than one destination from a state with a distinct input
At least one state has transitions that cannot be completely determined by
the input and its current state
It is possible to design a machine where a single input can have two paths
to an accepting state
Transitions
Move from a state without input

33

34. Conti …
An NFA is a five-tuple: ε = (Q, Σ, /, q0, F)
where
Q A finite set of states
Σ A finite input alphabet
q
0 The initial/starting state, q
0 is in Q
F A set of final/accepting states, which is a subset of Q
/ A transition function, which is a total function from Q x Σ to 2
Q
/: (Q x Σ) –> 2
Q
:2
Q
is the power set of Q, the set of all subsets of Q


34

35. NFA :example#1
An NFA accepting all strings that end in 01:



It is non-deterministic because input 0 in state q0 can lead to both q0 and q1.
:

X 1


{q
0,q
1}
{ } {q
2}

*
{ } { }
0
q
1q
2q
 
0
q
35

36. Example #2: pair of 0’s or pair of 1’s as substring
Q = {q0, q1, q2 , q3 , q4}
Σ = {0, 1}
Start state is q0
F = {q2, q4}

/: 0 1
q
0

q
1


q
2

q
3

q
4
{q
0, q
3} {q
0, q
1}
{} {q
2}
{q
2} {q
2}
{q
4} {}
{q
4} {q
4}
q
0
0/1
0
0
q
3
q
4
0/1
q
1
q
2
0/1
1
1
36

37. Formal approach to accepted strings
We are aiming to describe the language L(A)accepted by a NFA
A.
This description is similar to the DFA case, but a bit more
sophisticated.
As in the DFA case, we first define the extended transition
function:
That function will be used to define L(A).
Definition. The extended transition function of an NFA is defined as follow:
/^(q, 0) = q


)(: QpQX 




),('
'
),(),(
vqq
aqvaq






37

38. The language of an NFA
Intuitively, the language of a DFA A is the set of strings w that
lead from the start state to an accepting possible state.
Formally, the language L(A) accepted by the FA A is defined as
follows: L(A) = {w| ^(q0 ,w) F≠ }
38

39. Difference between NFA and DFA
Suppose that q is a state and a is an input symbol.
In a DFA, we have (q , a)  Q, that is, (q , a) is a state.
In a NFA, we have (q , a)  P(Q), that is,  (q , a) is a set of states, it can be seen as
the possible states that can result from input a in state q.
The difference between the DFA and the NFA is the type of transition function /
For a NFA / is a function that takes a state and input symbol as arguments (like the
DFA transition function), but returns a set of zero or more states (rather than
returning exactly one state, as the DFA must)
The only difference between a NFA and a DFA is in the type of value that / returns.
An NFA is like a DFA, except that it can be in several states at once
39

40. DFA vs. NFA
DFA
All transitions are deterministic
Each transition leads to exactly one
state
For each state, transition on all
possible symbols(alphabet) should be
defined
Accepts input if the last state is in F
(A string is accepted by a DFA, if it
transits to a final state)
Empty string transitions are not seen
Backtracking is allowed in DFA
Sometimes harder to construct
because of the number of states
Practical implementation is feasible
Requires more space




NFA
Transitions could be non-
deterministic
A transition could lead to a subset
of states
For each state, not all symbols
necessarily have to be defined in the
transition function
Accept input if one of the last states
in F (A string is accepted by a NDFA,
if at least one of all possible
transitions ends in a final state
NFA permits empty string transitions
In NFA, backtracking is not always
possible.
Generally easier than a DFA to
construct
Practical implementation has to be
deterministic(so need conversion to
DFA
Requires less space.
40

41. NFAs with 0 εoves
An NFA-0 is a five-tuple: ε = (Q, Σ, /, q0, F)
Q A finite set of states
Σ A finite input alphabet
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
/ A transition function, which is a total function from Q x Σ U {0} to 2Q
/: (Q x (Σ U {0})) –> 2Q
Sometimes referred to as an NFA-0 other times, simply as an NFA.
δet ε = (Q, Σ, /,q0,F) be an NFA-0.
A String w in Σ* is accepted by ε iff there exists a path in M from q0 to a state in F
labeled by w and zero or more 0 transitions.
The language accepted by ε is the set of all strings from Σ* that are accepted by ε.

41

42. Example:







/: 0 1 0
q
0 - A string w = w
1w
2…w
n is processed
as w = 0
*
w
10
*
w
20
*

… 0
*
w
n0
*

q
1 - Example: all computations on 00:

0 0 0
q
2 q
0 q
0 q
1 q
2
:
q
3

q
0
x
0/1
q
2
1
0
q
1
0
q
3
x
0
1
{q
0} { }

{q
1}
{q
1, q
2} {q
0, q
3} {q
2}
{q
2} {q
2} { }
{ } { } { }
42

43. 0-closure
Define 0-closure(q) to denote the set of all states reachable from q by zero or more 0
transitions.
Examples: (for the previous NFA)
0-closure(q0) = {q0, q1, q2} 0-closure(q2) = {q2}
0-closure(q1) = {q1, q2} 0-closure(q3) = {q3}
0-closure(q) can be extended to sets of states by defining:
0-closure(P) = 0-closure(q)
Examples:
0-closure({q1, q2}) = {q1, q2}
0-closure({q0, q3}) = {q0, q1, q2, q3}

Pq
q
0
0
0/1
q
2
1
0
q
1
0
q
3
0
0
1
43

44. Equivalence of DFAs and NFAs
Do DFAs and NFAs accept the same class of languages?
Is there a language L that is accepted by a DFA, but not by any NFA?
Is there a language L that is accepted by an NFA, but not by any DFA?
Are DFAs and NFAs Equivalent ?
The above questions turns, DFAs and NFAs accept exactly the same languages.
To show this we must prove every DFA can be converted into an NFA which
accepts the same language, and vice-versa.
Theorem. For every NFA N, there exists a DFA D such that L(D)=L(N).
Thus, a language L is accepted by some NFA if and only if it is accepted by
some DFA. Given N, we can effectively construct the corresponding D.
44

45. Conti …
Let N = be a NFA. The equivalent DFA D is obtained
from the so-called powerset construction (also called “subset construction”.) We define D =

Every NFA is an NFA-0.

Reading assignment ?
How Subset construction method works
Come up with Algorithms help to convert NFA s to their equivalent
DFAs
practice with the following conversions
NFADFA, -NFANFA, -NFA DFA
minimize number of states in a given FA
 
NN
NN
FqQ ,,,,
0


DD
DD
FqQ ,,,,
0

45

46. Chapter END up
46