Lecture Notes on Automata and Patterns (COMP11212)

Automata

babb X
Practical Example
·


Ab
abba v
Let I =
(a by ,
·




=
a E
aba v
We want to
·




identify any words over alphabet I such that they have an even numbers of as J
a, b
Let's draw an automata with two states [EVEN , ODD] for the numbers of as I've .
seen
> &
Da ,
b · a bab
X
F


· bb ~
b
6 b

a
x2 x2 abbar
W
ba
as abb X of

·..
↓ A
=
z
LVEN ODD
a



a




Deterministic Finite Automaton (DFA) DFA Acceptance

Definition 5: Let I be a finite alphabet of symbols. A (deterministic) finite "automaton Definition 6: A word S = X, ... An over E is accepted by the deterministic finite automaton
or DFA , over I consists of the following :

(Q 6) if
, 9 ., F,

·
A finite non-empty set Q of states ·
S(q ., x) =
91

·
A particular element ofQ called the start state (which we often ·
S(q1 ,*2) =
A2

denote with
qo) ...




·
A subset F of Q consisting of the accepting states ·
S(qn-1 <n) ,
=
An and


A transition EF ,
function & which for that accepting state
·

In
every state q Q
·
is
and , an is an
every
symbol zeI returns the next state 8(9 2) EQ
,
, so 8 is a



function from QXI to Q .
When S(q X) ,
=
q'we often write
.




G > q!·




We sometimes put these together
four items in a
quadruple
(Q , 9 ., F, 5)


Examples
Ab
Da b
c
,



>
a
D
Da b ,
>
S
D a

F



b a *
(ab(ba)(a(b)
b
*
(a(b)

&
a
W a
ab
*
a b
aab a(a(b)
A


↳ ba
a
> Da ,
b
a b
,
T




bs A




>
a
>
Da b , b
*
Jas
ja N

b dump state
(you cannot leave this state


aba 49 b ,



N



unreachable state




We can simplify it !
R
>



ja
b

, NFA Acceptance
Non-Deterministic Finite Automaton (NFA)
Definition 8 : Let I be a finite alphabet of symbols. A non-deterministic finite automaton Definitiona : A word S = X, ... Un over E is accepted by the non-deterministic finite
or NFA
,
over I is given by automaton (Q , q ., F, 6) if there are states


·
A finite non-empty set Q of states 90 , 91, .... q


·
A start state go in Q
such thatqo =
g .
and for all : < n
8 relates (gi , Xi) to gite and such
,


thatqn
A subset F of Q consisting of
is an
accepting state The language recognized by an NFA is the set
the accepting states
.

·




of words it accepts.


·
A transition relation s which relates a
pair consisting of a state and
a letter in I to a state. We often write
transitions from input
It means that it can have 2 or more a
given state for the same



G > Xq


if (q , 2 is S-related to 9

BFA us NFA


Example The key difference is in the transitions ,
for a DFA it is a
function whilst
for a NFA it is a


relation .




a Db abb
> · v Take this DFA
ba
N X
a) A
f(A
·
A =
a,b

b ·
ababb X
↑ b ,

L
· aab > A F
BDa f(A ,
b) = B
X

abbbab v b
B
f(B a)
·
=
,



b) A
f(B
=




f x
,
: > T




Rf (k f(x)z = X] ,)
(SA
=
DFA : B3 , A , (B3
,

,




=
NFA : (SA , BY A , ,
LBY , Rf




A DFA can be an NFA but an NFA cannot necessarily be a DFA
.
,




Algorithm 1: NFA to DFA


Given an NFA(Q , q ., F , 5) we can construct a DFA as
follows :
Examp1.
b
(P(Q)
a
,
,
39 . 3 , 15 [Q JqES with qEFY S , ↓
~
N
D
b
start state > A s > c


powerset of Q accepting states



P(Q) = [A , B, C , AB , AC , BC , ABC , ]
S' (S ,
x) =
GqEQ zgeS with q sta F = (C ,
Ac , BC , ABC)


unreachable
eb L unreachable
b -
Conly trasitions coming in
A C
>
B 3

D
b D
are also unreachable)
a

O
a, b b

*
b


AB Al BC



·
↳ a
D *
unreachable



a ,2
L
a




*
ABC L unreachable

↳ D




·


dump state



We can -

further simplify this


↳

Aub O
AC




&
so
AB


↳