deterministic finite state automata related

education related ppt. related to TOC.

1. Deterministic Finite Automata
(DFAs)

2. Real-Life Example: Finite Automaton
Controlling a computer-Generated
character
•States
–Attack
–Chase
–Spawn
–Wander
•Events
–E: see an enemy
–S: hear a sound
–D: die
Spawn
Wander
~E
D
Attack
~E
E
E
D
~S
inspect
E
S
S
D
Thief movie

3. Preliminary Definitions
•Given a set B, B* denote the set of all strings made of
elements in B. Strings in B* are also called words.
•For example, if  = {a,b}, then
* = {a, b, aa, ab, bb, …, baaaba, …}
•Given an DFA A = (Q,,,s,F) , A configuration is any
element in Q × *
•In the example in the previous slide possible configurations
include (s,abbba), (s, aaa), (q,bab) and (r, bbbb)
•The symbol e denotes the empty string

4. Configuration Yields Configuration
•Given an DFA A= (Q,,,s,F), the configuration (q,w)
yields the configuration (q’,w’) in one step, if w = w’ with
   and q’ = (q, )
q
q’

•(q,w) yields (q’,w’) if there is a sequence of configurations:
(q
1
,w
1
), (q
2
,w
2
), …, (q
k
,w
k
)
such that (q
i
,w
i
) yields (q
i+1
,w
i+1
) in one step

5. Example
1.What is the configuration yield after 3 yield-steps for
(s,aab)?
2.What is the configuration yield after 4 yield-steps for
(s,baab)?
s q
b
a
b
a
r
a
b
Trap/
Dead State
q
b
a
a
r
>

6. String Accepted by Automaton
•Given an automaton A = (Q,,,s,F), and a string w  *,
we say that w is accepted by A if the configuration (s,w)
yields the configuration (f,e), where f is a favorable state, and
e is the empty string
•In Example # 1, the automaton accepts aaabbbb but not b
•Given an automaton A, the language accepted by A,
written L(A), is defined by:

L(A) = {w  * : w is accepted by A}
“such that”
•The language accepted in Example # 1 is all the words that
contains two consecutive a’s

7. Example
•What is the language accepted by this finite automaton?
s q
b
a
b
a
r
a
b
Trap/
Dead State
q
b
a
a
r
>

8. Example # 2
What is the language accepted by this automaton?
s q
b
a
b
a
r
a
b
q
b
a
a
r
>