Lecture Notes on Automata and Patterns (COMP11212)
4 views 0 purchase
Course
Fundamentals of Computation (COMP11212)
Institution
The University Of Manchester (UOM)
Explore the intricate relationship between automata and pattern recognition with these comprehensive lecture notes for COMP11212. Learn about different types of automata, their role in recognizing patterns, and their applications in computational theory. Detailed explanations and visual aids help d...
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
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
↳
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.56. You're not tied to anything after your purchase.
