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
↳
