Unit 2
Finite Automata,
Nondeterminism,
Closure Properties
Dr. Nguyen Thi Thu Huong
Mobi: +84 903253796
Email: huongnt@[Link],
[Link]@[Link]
Introduction
• Automata theory is a wide applicable area
in Computer Science.
• Automata Theory is a part of our life.
• Have you ever seen a vendor machine , or
any equipment controlled by an automaton
like a washing machine, a traffic light, an
elevator, etc. ?
A vending machine
Opinions
• One uses, the Automata Theory in daily
life.
• If we know automata, we can understand
machines languages.
• Through Automata Theory one can learn
software, algorithm, and hardware basics.
• You are modeling some systems.
Modeling a finite automaton
• In Automata Theory, you can build your
own world and you can choose your rules.
• Automata Theory makes some relations to
hardware with software.
recognizers vs transducer
• There exist several types of finite-state
automata, which can be divided into two
main categories:
– recognizers: either accept the input or do not
– transducers: generate output from given
input
A recognizer example
• A branch of an Automaton for Vietnamese segmentation
• Express the relationship of morphemes in Vietnamese
phrase “thuộc địa bàn”
Simple Example – 1 way door
• Consider a one-way
automatic door.
• This door has two pads
that can sense when
someone is standing on
them, a front and rear
pad. Front Rear
Pad Pad
• We want people to walk
through the front and
toward the rear, but not
allow someone to walk
the other direction:
One Way Door
• Let’s assign the codes to our different input cases:
Nobody on either pad
Person on front pad
Person on rear pad
Person on front and rear pad
• We can design an automaton so that the door doesn’t open if
someone is still on the rear pad and hit them:
a,c,d b b,c,d
Start C O
a
State diagrams of finite automata
• State diagrams are directed graphs whose
nodes are states and whose arcs are
labeled by one or more symbols from
some alphabet Σ.
• One state is initial (denoted by a short
incoming arrow)
• Several states are final/accepting (denoted
by a double circle).
• DFA: For every symbol a∈Σ there is an arc
labeled a emanating from every state
Example
• State diagram of a DFA accepts all strings
over {a,b} that have 3 consecutive a’s.
• Consider 2 strings: abaab and baaab
– List of states for abaab: q0 q1 q0 q1
q2 q0 : string is not accepted
– List of states for baaab: q0 q0 q1 q2
q3 q3 : string is accepted
Formal Definition
of a Deterministic Finite Automaton (DFA)
A DFA is represented as the five-tuple: M = (Q, , δ,q0, F)
where
1. Q is a finite set of states,
2. is the alphabet of input symbols,
3. q0 Q is the start/initial state,
4. F Q Set of final states
5. : Q → Q is a transition function.
This function
• Takes a state and input symbol as arguments.
• Returns a state.
• One “rule” would be written δ(q, a) = p, where q and p
are states, and a is an input symbol.
• Intuitively: if the DFA is in state q, and input a is
received, then the DFA goes to state p (note: q = p OK).
DFA Example D1
• Recognize set of all
strings over{a,b} contain 3 a b
consecutive a’s q0 q1 q0
• Formal definiton q1 q2 q0
D1 = (Q, , δ,q0, F) q2 q3 q0
q3 q3 q3
Q = {q0, q1, q2, q3}, = {a,b},
F ={q3}
Configuration
• Used in formal description of DFA’s computation.
• Definition: Let M = (Q, , δ,q0, F) be a DFA. We say
that a word qx, qQ, x Σ*, is a configuration of M.
It represents the current state of M and the
remaining unread input of M.
• A configuration of a DFA,M, contains all the
information necessary to continue M’s computation.
• In programming parlance it is equivalent to a dump
of the current value of all variables of a program
and the current position in the program.
Language accepted by a DFA
• Let M = (Q, , δ,q0, F) be a DFA and let w = w1w2…wn be
a string where each wi is a member of alphabet .
• M accepts w if a sequence of states r0, r1, …, rn in Q exists
with three conditions:
1. r0 = q0 (the first configuration is q0w)
2. δ(ri, wi+1) = ri+1 for I = 0, … , n-1
3. rn F (the last configuration is rn)
• Language recognized by DFA M:
L(M) = {w | w * q0w * q F }
(In other words, the language is all of those strings that are
accepted by the finite automata).
Nondeterminism
• Nondeterministic Finite Automata
• NFA with - transition
Nondeterministic Finite Automata
• A NFA (nondeterministic finite automaton) is able to
be in several states at once.
– In a DFA, we can only take a transition to a single
deterministic state
– In a NFA we can accept multiple destination states for the
same input.
– Another way to think of the NFA is that it travels all possible
paths, and so it remains in many states at once. As long as
at least one of the paths results in an accepting state, the
NFA accepts the input.
• NFA is a useful tool
– More expressive than a DFA.
– BUT we will see that it is not more powerful! For any NFA
we can construct an equivalent DFA
NFA Example: N1
• NFA accepts set of all strings over {a,b} contain 3
consecutive a’s
• N1 includes 4 states like D1
Epsilon Transition
• Transition function δ is now a function that
takes as arguments:
– A state in Q and
– A member of {ε}; that is, an input symbol
or the symbol ε.Note that ε is not a symbol of
the alphabet .
Another NFA Example: N2
In this NFA, the string baaa is
accepted by the 2 paths
12231 and 123131.
In path 12231:12 matches b,
22 matches a, 23 matches a,
31 matches a.
In path 123131:12 matches b,
23 matches a, 31matches a,
13 matches ε, 31 matches a.
In other words, the accepted
string is baaεa.
Determinism vs Nondeterminism
Computation of N1 on baaab
Formal Definition of NFA
• Definition: An -NFA is represented as a
five – tuple (Q, , δ,q0, F) where
1. Q is a finite set of states,
2. is the alphabet of input symbols,
3. q0 Q is the start/initial state,
4. F Q Set of final states
5. : Q { {}}→ P(Q)
Formal Notation of NFA N1
N1 = (Q, , δ,q0, F)
Q = {q0, q1, q2, q3}, = {a,b}, F = {q3}
a b
q0 {q0,q1} {q0}
q1 {q2}
q2 {q3}
q3 {q3} {q3}
Formal Notation of NFA N2
N1 = (Q, , δ,q0, F)
Q = {q0, q1, q2, q3}, = {a,b}, F = {q3}
a b
1 {2} {3}
2 {2, 3} {3}
3 {1}
Language accepted by an NFA
• Same idea as the DFA
• Let N = (Q, , δ,q0, F) be an NFA and let w =
w1w2…wn be a string where each wi is a member
of alphabet ∑.
• N accepts w if a sequence of states r0r1…rn in Q
exists with three conditions:
1. r0 = q0
2. ri+1 δ(ri, wi+1) for i=0, … , n-1
3. rn F
Observe that δ(ri, wi+1) is the set of allowable next states
We say that N recognizes language A if A = {w | N accepts w }
Equivalence of DFA’s and NFA’s
• For most languages, NFA’s are easier to construct than
DFA’s
• But it turns out we can build a corresponding DFA for
any NFA
– The downside is there may be up to 2n states in turning a NFA
into a DFA. However, for most problems the number of states
is approximately equivalent.
• Theorem: A language L is accepted by some DFA if
and only if L is accepted by some NFA;
• i.e. : L(DFA) = L(NFA) for an appropriately constructed
DFA from an NFA.
– Informal Proof: It is trivial to turn a DFA into an NFA (a DFA is
already an NFA without nondeterminism). The following slides
will show how to construct a DFA from an NFA.
NFA to DFA : Subset Construction
• Let an NFA N be defined as N = (QN, , N, q0, FN)
• The equivalent DFA D = (QD, , D, q’0, FD), where
QD = P(QN); i.e. QD is the set of all subsets of QN (the power
set of QN). Often, not all of these states are accessible from
the start state; these states may be “thrown away”
• FD is the set of subsets S of QN such that S FN . That is,
FD is all sets of N’s states that include at least one accepting
state of N.
• For each set S QN and for each input symbol a in
• That is, to compute δD(S, a) we look at all the states p in S,
see what states of N goes to starting from p on input a, and
take the union of all those states.
Subset Construction Example
• Consider the NFA N2:
• The power set of these
states is: {Ø, {1},{2}, {3},
{1,2}, {1,3}, {2,3}, {1,2,3}}
a b
Ø Ø Ø
{1} {1,3} {2}
{2} {2,3} {3}
• New transition function {3} {1,3} Ø
with all of these states {1,2} {1,2,3} {2,3}
and go to the set of {1,3} {1.3} {2}
possible inputs. {2,3} {1,2,3} {3}
{1,2,3} {1,2,3} {2,3}
DFA D4 (equivalent to N4)
Observe that there is no path from state {1} to state {1,2} so {1,2} is remove from D4
Subset Construction (continued)
a b
Many states may be {1} {1} {2}
unreachable from our
start state. A good way to {2} {2,3} {3}
construct the equivalent {3} {1,3} Ø
DFA from an NFA is to
start with the start state {2,3} {1,2,3} {3}
and construct new states Ø Ø Ø
on the fly as we reach
them. {1,3} {1,3} {2}
{1,2,3} {1,2,3} {2,3}
Graphically:
Regular Languages
• Definition: a language is regular if and only
if some deterministic finite automaton
recognizes it
• Theorem: A language is regular if and only
if some nondeterministic finite automaton
recognizes it
Closure Properties
• We carry out operations on one or more
languages to obtain a new language
• It’s helpful when interesting properties are
preserved
• A variety of operations which preserve
regularity, i.e. the universe of regular
languages is closed under these operations:
union, intersection, complementation, star,
concatenation ….
Regular operations
• Union:
Example: 0 1;
• Concatenation: ° (In writing regular
expressions, no character is used to
represent this operation)
Example: 0 1
• Star*
Example: 0*
Theorem
• The class of regular languages is closed
under the union operation.
• PROOF IDEA
– Given regular languages L1 and L2 and want
to prove that L1 ∪ L2 is regular.
– The idea is to take two NFAs, N1 and N2 for L1
and L2, and combine them into one new NFA,
N
Construction of an NFA N to
recognize L1 ∪ L2
• Add a new
start state
that
branches to
the start
states of the
old machines
with ε arrows
Formal Description
Let N1 = (Q1, Σ, δ1, q1, F1) recognize L1,
N2 = (Q2, Σ, δ2, q2, F2) recognize L2.
Construct N = (Q, Σ, δ, q0, F) to recognize L1 ∪ L2.
1. Q = {q0} ∪ Q1 ∪ Q2.
2. The state q0 is the start state of N.
3. The set of accept states F = F1 ∪ F2.
4. Define δ so that for any q ∈ Q and any a ∈ Σ ∪ ε,
δ(q, a) = δ1(q, a) if q ∈ Q1
δ2(q, a) if q ∈ Q2
{q1, q2} if q = q0 and a = ε
∅ if q = q0 and a ≠ ε.
Theorem
• The class of regular languages is closed under
the concatenation operation
• PROOF IDEA Take two NFAs, N1 and N2 for L1
and L2, and combine them into a new NFA N
– Assign N’s start state to be the start state of N1.
– The accept states of N1 have additional ε arrows to the
start state of N2
– The accept states of N are the accept states of N2
– N accepts when the input can be split into two parts,
the first accepted by N1 and the second by N2
Construction of N to recognize L1 L2
Formal description
Let N1 = (Q1, Σ, δ1, q1, F1) recognize L1,
N2 = (Q2, Σ, δ2, q2, F2) recognize L2.
Construct N = (Q, Σ, δ, q1, F2) to recognize L1 L2.
1. Q = Q1 ∪ Q2.
2. The start state q1 is the same as the start state of N1.
3. The accept states F2 are the same as the accept states of N2.
4. Define δ so that for any q ∈ Q and any a ∈ Σ ∪ ε,
δ(q, a) = δ1(q, a) q ∈ Q1 and q F1
δ1(q, a) q ∈ F1 and a ≠ ε
δ1(q, a) ∪ {q2} q ∈ F1 and a = ε
δ2(q, a) q ∈ Q2.
Theorem
• The class of regular languages is closed
under the star operation.
• Proof idea
– Take an NFA N1 for L1 and modify it to recognize
L1∗
– N like N1 with additional ε arrows returning to
the start state from the accept states.
– Modify N so that it accepts ε
Construction of N to recognize L1∗
Formal description
• Let N1 = (Q1, Σ, δ1, q1, F1) recognize L1.
Construct N = (Q, Σ, δ, q0, F) to recognize L1∗ .
1. Q = {q0} ∪ Q1.
2. The state q0 is the new start state.
3. F = {q0} ∪ F1.
δ(q, a) = δ1(q, a) if q ∈ Q1 and q F1
δ1(q, a) if q ∈ F1 and a ≠ ε
δ1(q, a) ∪ {q1} if q ∈ F1 and a = ε
{q1} if q = q0 and a = ε
∅ if q = q0 and a ≠ ε.