deterministic finite state automata related ppt

education related ppt of theory of computation

1. Deterministic Finite Automata
(DFAs)

2. Reminder: Functions vs Relations
Let P = {p: p is a person}
M = {m: m is a male}
S
1
= {(m,p): m is in M, p is in P and m is the father of m}
S
2 = {(m,p): m is in M, p is in P and m is an ancestor of m}
1.True or false: S
1
 M  P
2.True or false: S
2  M  P
3.Is either S
1
or S
2
a relation in M  P?
4.Is either S
1
or S
2
a function f:M  P?

3. Deterministic Automata
(Informal)
Key questions: if a automaton is confronted with a certain
state where a choice must be made,
1. are all the alternatives transitions known?, and
2. given some input data, is it known which transition the
machine will make?
If the answer to both of these
questions is “yes”, the automaton
is said to be deterministic
“current state”
“transition”
“new state”

4. Nondeterministic Automata
(Informal)
If the answer to any of these questions is “no”, the
automaton is said to be nondeterministic
That is, either
• some transitions are unknown, or
• given some input data, the machine can make more
than one transition

5. Deterministic Automata
(Informal)
We are going to define automata indicating for a state s and
some input data d, which is the state that will be reached
Transition: ((s,d), s’)
s
d s’
Let Q be the set of all states and  be the set of all input data.
Then, the set of transitions is a subset of (Q  )  Q
of the computation

6. Determinism, Nondeterminism,
Relations and Functions
The set of transitions defining an automaton is a subset of
(Q  )  Q
If the automaton is deterministic, should the set of transitions be
a relation or a function?
• Deterministic automata: Since for each pair (s,d) there
should be one and only one s’, the set of transitions must be
a function
• Nondeterministic automata: Since for each pair (s,d)
there might not be any s’ or there might be more than one
s’, the set of transitions must be a relation

7. Finite Automata
•Problem 1: Design a computer program that given a sequence
of numbers a
1
, a
2
, …, a
n
returns their sum a
1
+ a
2
+… + a
n

•Problem 2: Design a computer program that given a sequence
of numbers a
1
, a
2
, …, a
n
returns the list in the inverted order:
a
n
, …, a
2
, a
1

•How many memory units are needed for a program to execute:
 problem 1:
Problem 2:
Finite automata use a constant amount of memory
1
n

8. Deterministic Finite Automaton (DFA)
A deterministic finite automaton (DFA) is a 5-tuple (Q,,,s,F)
where:
•Q is a finite set of elements called states
 is a finite input alphabet
 is a transition function, (Q × ) × Q (or : (Q × )  Q)
•s  Q called the initial state
•F  Q called the favorable states
…
a
1
a
2
Constant!
The fact that  is a function
makes the automaton
deterministic
no! (or yes!)