Chapter 2: Finite Automata
Objectives
Mastering the following concepts:
–Deterministic Finite Accepter (DFA)
–Nondeterministic Finite Accepter (NFA)
–DFA and NFA Equivalence
Deterministic Finite Accepter (DFA)
M = (Q, ∑, δ, q0, F)
Q: finite set of internal states
∑: finite set of symbols - input alphabet
δ: Q × ∑ → Q transition function
q0∈Q: initial state
F⊆Q: set of final states
Operational Mechanism
Control unit
q0
Input file
yes/no
Question: What is the
difference between a
general automaton and
a DFA?
Transition Graph
M = (Q, ∑, δ, q0, F)
•|Q| vertices (circles)
•Edge (qi, qj) labelled a for δ(qi, a) = qj
•Initial vertice q0
•Final vertices (double circles) in F
