close

Вход

Log in using OpenID

embedDownload
Chapter 4
Finite Automata
Models of Computation
2
Different Kinds of Automata
• Automata are distinguished by the temporary
memory
• Finite Automata
:
no
temporary memory
• Pushdown Automata
• Turing Machines
Sept2011
:
stack
:
random
access memory
Theory of Computer Science
3
Finite Automaton
temporary memory
Finite
Automaton
input memory
output memory
Example: Vending Machines
(small computing power)
4
Pushdown Automaton
Stack
Push, Pop
Pushdown
input memory
Automaton
output memory
Example: Compilers for Programming Languages
(medium computing power)
5
Turing Machine
Random Access Memory
Turing
input memory
Machine
output memory
Examples: Any Algorithm
(highest computing power)
6
Power of Automata
Finite
Pushdown
Turing
Automata
Automata
Machine
Less power
More power
Solve more
computational
problems
Sept2011
Theory of Computer Science
7
Finite Automata
http://www.youtube.com/watch?v=d7ZAcym3DUw
8
Finite Automata (FA)
• Finite - Every FA has a finite number of
states
• Automata (singular automaton) means
“machine”
• A simple class of machines with limited
capabilities.
• Good models for computers with an
extremely limited amount of memory.
• E.g., an automatic door : a computer with
only a single bit of memory.
9
Examples
• Elevator controller
– state : n-th floor
– input : input received from the buttons.
•
•
•
•
Dishwashers
Washing Machines
Digital watches
Calculators
10
State Diagram
LIFT:
• move to level 1 when person push button 1
• move to level 2 when person push button 2
• move to level 3 when person push button 3
Level
3
Level
2
Level
1
11
State Transition Table
States:
Input:
Level1, Level2, Level3
1 someone push button 1
2 someone push button 2
3 someone push button 3
INPUT
STATE
Level1
Level2
Level3
1
2
3
Level1
Level1
Level1
Level2
Level2
Level2
Level3
Level3
Level3
12
Finite Automaton
Input
String
Output
Finite
Automaton
“Accept”
or
“Reject”
13
Definition of FA
• A finite automaton (FA) is a collection of 3
things:
– A finite set of states, one of them will be the
initial or start state, and some (maybe none)
are final states.
– An alphabet  of possible input letters.
– A finite set of transition rules that tell for
each state and for each input (alphabet)
which state to go to next.
14
State Diagram
transition
Initial /
start
state
final /
accepting
state
– start state = q1
state
– final state = q2
– transitions = each arrows
– alphabet = each labels
• When this automaton receives an input string such as 1101, it
processes that string and produce output (Accept or Reject).
15
Initial Configuration
a b b a
Input String
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a, b
q4
16
Reading the Input
a b b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
17
a b b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
18
a b b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
19
a b b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
20
Input finished
a b b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
accept
21
Rejection
a b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
22
a b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
23
a b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
24
a b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
25
Input finished
a b a
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
reject
a,b
q4
26
Another Rejection

a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
27

a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
reject
28
Language of Machine
• If A is the set of all strings accepted by machine M,
we say that A is the language of machine M.
L(M) = A
• L(M) = {strings that bring M to an accepting state}
• M recognizes A (only 1 language)
• M accepts strings (several strings)
• If M accepts no strings, it still recognizes one
language, empty language 
29
Formal Definition
•
A finite automaton is a 5-tuple
(Q, , , q0, F) where
–
–
–
–
–
Q is a finite set of states,
 is a finite set of alphabets,
 : Q x   Q is the transition function,
q0  Q is the start state, and
F  Q is the set of accept states (final states)
Note:  - delta
30
Example :
Finite Automaton M1
• M1= (Q,,,q1,F) , where
– Q = {q0, q1},
–  = {a, b},
–  is described as
– q0 is the start state, and
– F = {q0, q1}.
a
b
q0
q0
q1
q1
q0
q1
31
Example :
Finite Automaton M1
What is the
language of
M1?
L(M1) = (a + b)*1+00+01)*
32
Example :
Finite Automaton M2
0
1
1
q2
q1
0
• M2 = (Q, , , q0, F) , where
–Q=
–=
–  is described as
– q1 is the start state, and
– F = { }.
0
1
q1
q2
33
Example :
Finite Automaton M2
0
1
1
q2
q1
0
What is the language of M2?
L(M2) = {w | w ends in a 1}
34
Empty String 
0
1
q1
1
q2
0
• If the start state is also a final state, what
string does it automatically accept ?
• L(M3) = { w | w is the empty string  or
ends in a 0}
35
Example :
Finite Automaton M4
• M4= (Q, , , S, F) , where
S
b
a
a
r1
q1
b
a
q2
b
b
a
b
r2
a
– Q=
r1
– =
–  is described as S
a
b
q1
r1
q1
q1
q2
q2
q1
q2
r1
r2
r1
r2
r2
r1
– S is the start state, and
– F = { q1, r1 }.
L(M4) = strings that start and end with the same symbol.
# a(a + bb*a)* + b(b + aa*b)*
36
FA Design : Example
• Question: Design an FA to accept the language
of all strings over {0, 1} that contain the string
001 as a substring, e.g.: accept 0010, 1001,
001, 111001111, but not 11, 000.
• Thinking of… for every input, skip over all 1s. If
we read 0, note that we may have just seen
the first of the 3 symbols 001. Then if we see a
1, go back to skipping over 1s. Then … proceed
… to seek for another two 0s ...
Theory of Computer Science
37
Example : Strings with substring 001
• So we can conclude there are four possibilities:
– Haven’t just seen any symbols of 001
– Have just seen a 0
– Have just seen 00
– Have seen 001
• Assign the states q, q0, q00, q001 to these possibilities. We can
design the transition by observing that from q reading a 1,
we stay in q, but reading a 0 we move to q0. In q0, reading a 1
we return to q, but reading a 0 we move to q00. In q00,
reading a 1 we move to q001, but reading a 0 leaves us in q00.
finally, in q001 reading a 0 or a 1 leaves us in q001.
Theory of Computer Science
38
Example : Strings with substring 001
• The start state is q, and the only accept state is q001.
or
Theory of Computer Science
39
Designing a FA – An example
• Draw an FA accepting the language of all
string over {a, b} containing exactly two a’s.
• b*ab*ab*
• IN aa, aba, baba, aabb, bbbaa.
• NOT a, ab, ba, bb
Sept2011
Theory of Computer Science
40
How to convert RE to FA
• General rules:
• a+b
• ab
• a*
Sept2011
Theory of Computer Science
41
How to convert RE to FA
• ab*a – aa, aba, abba, abbba.
• (a + b)c – aa, bc
• a(bc)* – a, abc, abc
Sept2011
Theory of Computer Science
42
Computation of FA, ⊢M
• Way to describe the computation of a DFA
• What state the DFA is currently in, and what string is left to
process
– (q0, 0010) Machine is in state q0, has 0010 left to process
– (q1, 010) Machine is in state q1, has 010 left to process
– (q3, ) Machine is in state q3 at the end of the
computation (accept iff q3 ∈ F)
• Binary relation ⊢M : What machine M yields in one step
– (q0, 0010) ⊢M (q1, 010)
Theory of Computer Science
43
Accepted @ Rejected Strings
• To trace all computations that process the
string 0010.
• [q0 , 0010] ⊢ [q1 , 010]
⊢ [q2 , 10]
⊢ [q3 , 0]
⊢ [q3 , λ]
• Stop at q3 (final state) and all alphabet is
traced (string is empty);
• Hence, string 0010 is accepted by machine.
Theory of Computer Science
44
Determinism
• So far, every step of a computation
follows in a unique way from the
preceding step.
• When the machine is in a given state
and reads the next input symbol, we
know what the next state will be – it is
called deterministic computation
• Deterministic Finite Automata (DFA)
45
Why DFA?
• Why are these machines called
“Deterministic Finite Automata”
• Deterministic - Each transition is
completely determined by the current
state and next input symbol. That is, for
each state / symbol pair, there is exactly
one state that is transitioned to.
Sept2011
Theory of Computer Science
46
Nondeterminism
• In a nondeterministic machine, several
choices may exist for the next state at any
point.
• Nondeterministic Finite Automata (NFA)
• Nondeterminism is a generalization of the
determinism, so every DFA is
automatically a NFA.
47
Example of DFA vs. NFA
DFA
NFA
48
Differences between
DFA & NFA
• Every state of DFA always has exactly
one exiting transition arrow for each
symbol in the alphabet while the NFA
may has zero, one or more.
• In a DFA, labels on the transition
arrows are from the alphabet while
NFA can have an arrow with the label .
49
One exiting transition arrow
 q0 , 1  q1
0
q0
1
q1
0, 1 q
2

50
More (two) exiting transition arrows
 ( q1,0)  {q0 , q2 }
0
q0
1
q1
0, 1 q
2

51
More (two) exiting transition arrows
 ( q0 ,  )  {q0 , q2}
0
q0
1
q1
0, 1 q
2

52
Zero exiting transition arrow – undefined
transiton
 ( q2 ,1)  
0
q0
1
q1
0, 1 q
2

53
NFA vs. DFA
Features
DFA
NFA
Choice of transition
Single
Multiple
Input label
Alphabets only Alphabets or  or 
Undefined transitions No
Possible
• Converting NFA to DFA
• Remove all undefined states into trap state(s)
• Remove empty string inputs ( or )
• Remove multiple states transitions
54
How does the NFA work?
• When we are at a state with multiple choices to proceed
(including  symbol), the machine splits into multiple
copies of itself and follow all the possibilities in parallel.
• Each copy of the machine takes one of possible ways to
proceed and continuous as before. If there are
subsequent choices, the machine splits again.
• If the next input symbol doesn’t appear on any of the
arrows exiting the state occupied by a copy of the
machine, that copy dies.
• If any one of these copies is in an accept state at the end
of the input, the NFA accepts the input string.
55
Tree of possibilities
• Think of a nondeterministic computation as a
tree of possibilities
• The root of the tree corresponds to the start
of the computation.
• Every branch point in the tree corresponds to
a point in the computation at which the
machine has multiple choices.
• The machine accepts if at least one of the
computation branches ends in the an accept
state.
56
Tree of possibilities
Deterministic
computation
start
Nondeterministic
computation
reject
accept or reject
accept
57
Example: 010110
Start
Read symbol
q1
0
q1
1
q2
q1
q3
0
q3
q1
1
q1
q2
q3
q4
1
q1
q2
q3
q4
q4
0
q1
q3
q4
q4
58
Properties of NFA
• Every NFA can be converted into an equivalent
DFA.
• Constructing NFAs is sometimes easier than
directly construction DFAs.
• NFA may be much smaller than it DFA
counterpart.
• NFA’s functioning may be easier to understand.
• Good introduction to non-determinism in more
powerful computational models because FA
are especially easy to understand.
59
Example:
Converting NFA into DFA
NFA: recognizes language which contains 1 in the
third position from the end
Equivalent DFA:
60
Formal definition of NFA
• A NFA is a 5-tuple (Q, , , q0, F) , where
– Q is a finite set of states,
–  is a finite alphabet,
–  : Q x   P(Q) is the transition function,
– q0 is the start state, and
– F  Q is the set of accept states.
Notation:
P(Q) is called power set of Q (a collection of all subsets of Q).
and
 = {}
61
Example:
Formal definition of NFA
NFA M1:
• Formal definition of N1 is (Q, , , q0, F) , where
– Q = {q1,q2,q3,q4}
–  = {0,1}
–  is given as
– q0 is the start state, and
– F = {q4}
q1
q2
q3
q4
0
{q1}
{q3}

{q4}
1
{q1,q2}

{q4}
{q4}


{q3}


62
Example of NFA
• L = {w ∈ {a, b} : w starts with a}
• What is the RE for the language? a(a+b)*
• What happen if the 1st input is b?
Theory of Computer Science
63
Example of NFA
• L = {w ∈ {a, b} : w contains the substring aa}
• What is the RE for the language? (a+b)*aa(a+b)*
• What happen if the 1st input is a?
• Does the machine accept abaa?
(q0, abaa)
(q0, baa)
(q1, baa) reject
Sept2011
(q0,aa)
(q0, a)
(q1, a)
Theory of Computer Science
(q0, e) reject
(q1, e) reject
(q2, e) accept
64
Regular Languages
Definition:
• A language L is regular if there is FA M
such that L = L(M)
Observation:
• All languages accepted by FAs form the
family of regular languages
65
Regular Languages
• Examples of regular languages:
{abba}
{, ab, abba}
{awa : w  {a, b}*} {anb : n  0}
{all strings with prefix ab}
{all strings without substring 001}
There exist automata that accept these
languages.
66
Non-Regular Languages
• There exist languages which are not
regular :
• Example :
n
n
L = {a b : n  0}
There is no FA that accepts such a
language.
67
Example of DFA
• L(M) = {anb : n  0}
a, b
a
q0
b
q1
accept
a,b
q2
trap state
68
Example of DFA
• L(M) = {, ab, abba}
M
a,b
q5
b
q0 a
accept
a
a
b
q1 b q2 b q3 a
accept
a,b
q4
accept
69
Example of DFA
•
•
•
•
Input Alphabet  = {a, b}
Set of States Q = {q0, q1, q2, q3, q4, q5}
Initial State = q0
Set of Accepting States F = {q4}
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
70
Transition Functions ()
• :QxQ
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
71
 q0 , a   q1
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
72
 q0 , b   q5
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
73
 q2 , b   q3
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
74

q0
q1
q2
q3
q4
q5
a
q1
q5
q5
q4
q5
q5
b
q5
q2
q3
q5
q5
q5
Transition Function ()
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
75
Extended Transition Function (*)
• * : Q x *  Q
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
76
• * (q0, ab) = q2
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
77
• * (q0, abba) = q4
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
78
• * (q0, abbbaa) = q5
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
79
Observation: if there is a walk from q to q’
with label w then
* (q, w) = q’
w
q
q
W = 1 2 …k
q
1
2
k
q
80
Example: There is a walk from q0 to q5
with label abbbaa
* (q0, abbbaa) = q5
a,b
q5
b
q0 a
a
a
b
q1 b q2 b q3 a
a,b
q4
81
Language Accepted by FAs
• For a FA M = (Q, , , q0, F)
• Language accepted by M :
L(M) = (w  *: *(q0, w) F)
q0
w
q  q
F
82
Observation
• Language rejected by M :
L(M) = (w  *: *(q0, w)  F)
q0
w
q q 
F
83
Example (NFA or DFA ?)
• Create a FA for L(M) = {awa : w  {a, b}*}
a, b
q0
a
q2
a
q3
• What happen if the 1st input is b?
• What happen if the input are bab, abab, … ?
84
Example of DFA
• L(M) = {awa : w  {a, b}*}
b
a
b
q0
a
q2
q3
a
b
q4
a,b
85
Example
• L(M) = {all strings without substring 001}
0
1
0,1
1
0

0
00
1
001
0
86
Example
• L(M) = {all strings with prefix ab}
a,b
q0
a
b
q1
b
accept
a
q3
q2
a,b
87
Regular Grammars , Finite Automata and Regular Expression
A context-free grammar is called regular if each rule is the form.
A → aB , A → a , or A → λ
Let grammar G be:
G : S → aS | aA | λ
A → bA | b
a
M:
S
a
A
Regular Grammars , Finite Automata and Regular Expression
A context-free grammar is called regular if each rule is the form.
A → aB , A → a , or A → λ
Let grammar G be:
G : S → aS | aA | λ
A → bA | b
a
M:
S
b
a
A
b
Z
Derivation
Computation
S→ aS
[ S, aabb]┣ {S, abb]
String processed
a
→aaA
┣ [A, bb]
aa
→aabA
┣ [A, b]
aab
→aabb
┣ [A, λ]
aabb
Derivation
Computation
S→ aS
[ S, aabb]┣ {S, abb]
String processed
a
→aaA
┣ [A, bb]
aa
→aabA
┣ [A, b]
aab
→aabb
┣ [ Z, λ]
aabb
Regular Grammars , Finite Automata and Regular Expression
Let grammar G be:
S → a* aA + λ
G : S → aS | aA | λ
A → bA | b
A→ b* b
S → a* ab*b + λ
Thus, regular expression for grammar G or NFA M is:
a+b+ + λ
a*ab*b + λ
OR
a
M:
S
b
a
A
b
Z
Example
Let grammar G be:
G : S → aS | bB | a
B → bB | λ
M:
a
b
B
S
a
Z
Example
Let grammar G be:
G : S → aS | bB | a
B → bB | λ
M:
b
a
b
B
S
a
Z
Example
Let grammar G be:
G : S → aS | bB | a
B → bB | λ
S → a*bB + a*a
B → b*
S → a*bb* + a*a
M:
b
a
b
B
S
a
Z
The regular expression is:
a*bb* + a*a
OR
a*(bb* + a)
Example
A regular grammar with alphabet { a, b } that generates strings with
an even number of a’s and an odd number of b’s.
b
B
a
b
a
S
a
b
C
a
b
A
S → aB | bA | λ
A → aC | bS
B → aS | bC
C → aA | bB
Example: NFA to DFA
The NFA. M accepted the language a+ b+
M:
a
qo
b
q1
a
b
a
b
q0
{q0, q1}
Ø
q1
Ø
{q1, q2}
q2
Ø
Ø
q2
Example: NFA to DFA
The NFA. M accepted the language a+ b+
a
b
qo
{q0, q1}
Ø
q1
Ø
{q1, q2}
q2
Ø
Ø
DM :
a
a
b
{qo}
{qo ,q1}
b
{q1,q2}
a
ø
a,b
b
Exercise
• For the alphabet {0, 1} give regular expression and
finite automata for each language:
– All strings containing exactly two 0’s.
– All strings containing at least two 0’s.
– All strings containing 00 as substring.
• For the alphabet {a, b} give NFA for each language:
– 1. All strings starting with abb.
– 2. All strings ending with abb.
– 3. All strings containing abb as a substring.
Sept2011
Theory of Computer Science
98
1/--pages
Пожаловаться на содержимое документа