Transcript 2-finite_automata - CIS @ Temple University

2. Finite Automata
CIS 5513 - Automata and Formal Languages – Pei Wang
Deterministic finite automata
A deterministic finite automaton (DFA)
A = (Q, ∑, δ, q0, F) where
 Q is a finite set of states
 ∑ is the alphabet of input symbols
 δ: Q×∑ → Q, a transition function that
specifies the state change given an input
 q0  Q, the start state
 F  Q, the final (accepting) states
Example of DFA
Define a DFA that accepts language
L = { x01y | x and y are binary strings }
 ∑ = {0,1}
 Q = {q0, q1, q2}
 F = {q1}
 δ: represented as the following transition
diagram or table
Example of transition function
Extended transition function
δ is extended into δ^ (delta-hat): Q×∑* → Q
 δ^(q, ϵ) = q
 δ^(q, xa) = δ(δ^(q, x), a)
Example: L = {w | w has both an even number
of 0’s and an even number of 1’s}
Extended transition function (cont.)
DFA and regular language
For a given DFA
A = (Q, ∑, δ, q0, F)
the language it accepts is
L(A) = { w | δ^(q0, w)  F }
Such a L is called a regular language
Kleene’s theorem:
A language over an alphabet is regular if and
only if it can be accepted by a finite automaton
Exercise 2.2.1(a)
Solution:
http://infolab.stanford.edu/~ul
lman/ialcsols/sol2.html#sol22
More exercises
Exercise 2.2.4(a): Given a DFA that accepts the set of all binary strings
ending in 00
Exercise 2.2.6(a): Given a DFA that accepts the set of all binary strings that
are binary numbers divisible by 5
Exercise 2.2.10(a): Consider the DFA defined as ({A, B}, {0, 1}, δ, A, {B})
where δ(A, 0) = A, δ(A, 1) = B, δ(B, 0) = B, δ(B, 1) = A. What language
does it accept? Prove the conclusion
Solutions: http://infolab.stanford.edu/~ullman/ialcsols/sol2.html#sol22
Nondeterministic finite automata
A NFA has a transition function δ: Q×∑ → 2Q
δ(q, a) is a set of states that it may be in
Other interpretations: a NFA can explore
accepting possibilities in parallel, or can guess
about the future input
Example: to accept binary strings {x01}
Here δ only specifies possible ways to accept
Extended transition in NFA
Extending δ into δ^: Q×∑* → 2Q in an NFA:
 δ^(q, ε) = {q}
 δ^(q, xa) = δ(pi,a), where piδ^(q,x)
NFA and regular language
For a given NFA
A = (Q, ∑, δ, q0, F)
the language it accepts is
L(A) = { w | δ^(q0, w) ∩ F  Ø }
A word is accepted if it may lead to a final state
Such an L is also a regular language
A DFA can be converted into an equivalent NFA
by changing each δ(p, a) = q into δ(p, a) = {q}
NFA to DFA
For a given NFA N, a DFA D can be constructed
so that L(D) = L(N)
For N = (QN, ∑, δN, q0, FN), the corresponding
D = (QD, ∑, δD, {q0}, FD):
 QD is the power set of QN
 δD(S, a) = δN(p, a) for each p  S
 FD is the set containing all subsets of QN with
non-empty intersection with FN
Example of NFA to DFA
Example of NFA to DFA (cont.)
After removing the states inaccessible from the
start, the resulting DFA is:
NFA to DFA: approaches
There are two approaches in specifying QD:
1. Exhaustively generate the power set of QN,
then remove the inaccessible ones
2. Begin from the start state, and only list the
accessible states
The state corresponding to empty set of states
in N may be an accessible state in D
More examples
Exercise 2.3.4(a): Give an NFA to accept the set of digit strings such
that the final digit has appeared before
Solutions: http://infolab.stanford.edu/~ullman/ialcsols/sol2.html#sol23
Text search
NFAs with epsilon-transitions
An ε-transition in
an NFA changes
state with an
empty string as
input
2.18: A decimal
number can be
12.4, 0.34, -.01,
and +3., but not
123 or .
Epsilon-NFA
An ε-NFA has δ: Q×(∑{ε}) → 2Q , i.e., it may
take ε as the second argument to form
“ε-transitions”
The ε-closure of a state q is the set of states
that can be reached from q with ε-transitions
Given any ε-NFA, a DFA can be built to accept
the same language like given a NFA, except
that the ε-closures of state sets are used
Exercise 2.5.1
Solutions: http://infolab.stanford.edu/~ullman/ialcsols/sol2.html#sol25