CSC236H5F Non-Deterministic Finite Automata
Non-Deterministic Finite Automata
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSC236H5F
Non-Deterministic Finite Automata (NFA)
Outline
Minimal number of states for a DFA
A non-regular language
Non-deterministic Finite Automaton (NFAs)
NFA −→ DFA
Equivalence
Recall
Let us consider the following language from last time
L = {w ∈ {0, 1}∗ | the third symbol of w is 1} (1)
We claimed that this cannot be recognized by a DFA with 4 states.
Recall
Let us consider the following language from last time
L = {w ∈ {0, 1}∗ | the third symbol of w is 1} (1)
We claimed that this cannot be recognized by a DFA with 4 states.
Proof.
Number of DFA States
▶ For similar-looking regexes, the number of required DFA
states can be quite different
▶ 5-state DFA: (0 + 1)(0 + 1)1(0 + 1)∗
▶ 8-state DFA: (0 + 1)∗1(0 + 1)(0 + 1)
▶ Why more states?
▶ The DFA doesn’t know how many of the initial symbols the
star should take
▶ It would be nice to be able to guess whether the next symbol
should be consumed by the star or whether it will end up being
the third-last symbol
Outline
Minimal number of states for a DFA
A non-regular language
Non-deterministic Finite Automaton (NFAs)
NFA −→ DFA
Equivalence
An example
Consider the language L over Σ = {0, 1}, given by
L
def
=
{
0n1n : n ∈ N
}
(2)
We claim that no DFA recognizes L.
An example
Consider the language L over Σ = {0, 1}, given by
L
def
=
{
0n1n : n ∈ N
}
(2)
We claim that no DFA recognizes L.
Proof.
Outline
Minimal number of states for a DFA
A non-regular language
Non-deterministic Finite Automaton (NFAs)
NFA −→ DFA
Equivalence
Nondeterministic Finite Automata (NFAs)
q0
0,1
q11 q20,1 q30,1
▶ This isn’t deterministic anymore!
▶ Reading a 1 in q0 can lead back to q0 or to q1
▶ For any string whose third symbol from the right is a 1, there
is a path that gets us to q3
▶ Let’s practice with the string 0101110
Formal Definition of a Non-deterministic Finite Automaton
Definition
A Finite Automaton is a 5-tuple (Q,Σ, δ, q0,F ) where:
1. Q is a finite set, called the set of states.
2. Σ is a finite set, called the alphabet.
3. δ : Q × Σ −→ 2Q is the transition function.
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.
Outline
Minimal number of states for a DFA
A non-regular language
Non-deterministic Finite Automaton (NFAs)
NFA −→ DFA
Equivalence
ConcepTest
Consider
L =
{
w ∈ {a, b}∗ | w starts with a and ends with b
}
(3)
A minimal DFA for L has 4 states. How many states are there in a
minimal NFA for L?
A. 2
B. 3
C. 4
D. 5
Exercise: Developing NFA
Let
L =
{
w ∈ {a, b, c}∗ such that the second-last and
third-last characters of w are the same
}
(4)
Develop an NFA for L. Try to develop an NFA with the minimum
number of states!
ConcepTest
Which of the following strings is accepted by the above ϵ-NFA?
A. abab
B. ba
C. bbb
D. Two of the above
E. None of the above
Outline
Minimal number of states for a DFA
A non-regular language
Non-deterministic Finite Automaton (NFAs)
NFA −→ DFA
Equivalence
Equivalence of Representations
Regular expressions, DFAs, NFAs, and NFAs with ϵ-transitions all
recognize exactly the same subset of languages: the regular
languages!
Let L be a language over an alphabet Σ. Then the following are
equivalent:
(1) There is a regular expression that matches L
(2) There is a DFA that accepts L
(3) There is an NFA and an ϵ-NFA that accept L
Equivalence of Representations...
Here’s one way to prove the equivalences:
▶ Given an NFA, show how to construct a DFA that accepts the
same language (Subset Construction)
▶ Given a DFA, show how to construct a regex that accepts the
same language (Transitive Closure)
▶ Given a regex, show how to construct an NFA that accepts
the same language (see notes)
Subset Construction
The Subset Construction algorithm takes an NFA and produces a
DFA that accepts the same language.
▶ Define e(q) as the set of states reachable from q by taking
zero or more ϵ-transitions
▶ The start state of the DFA is e(s) for start state s of the NFA
▶ We treat each DFA state as a collection of NFA states
Subset Construction...
▶ Repeat until no more states are added
▶ For some state q in the DFA, let p be the set of corresponding
states in the NFA
▶ For symbol a, determine the set of NFA states r reachable
from some state in p
▶ Compute e(r). This is the state reached by the DFA from q on
symbol a
▶ The accepting states of the DFA are those states that contain
at least one accepting state of the NFA
Exercise: Subset Construction
The start state is q0; the accepting state is q3.
Current State Symbol New State
q0 0 q0
q0 1 q0
q0 1 q1
q1 0 q2
q1 1 q2
q2 0 q3
q2 1 q3
Use the Subset Construction algorithm to create an equivalent
DFA for the above NFA.
Transitive Closure
The Transitive Closure algorithm takes a DFA and produces a
regular expression that accepts the same language.
▶ Number the states of the DFA as Q = {1, . . . , n}
▶ Define Li ,j as a regular expression matching those strings that
take the DFA from state i to state j
▶ Define Li ,j(k) as a regular expression matching those strings
that take the DFA from state i to state j with only states ≤ k
allowed between i and j
▶ k can be 0, which means that no state is allowed between i
and j
ConcepTest
Current State Symbol New State
q1 0 q2
q1 1 q1
q1 2 q3
q2 1 q1
q2 0 q4
q2 2 q4
q3 0 q1
q3 1 q1
q3 2 q3
q4 0 q4
q4 1 q4
q4 2 q4
What is L2,3(0)?
A. {}
B. ϵ
C. 0
D. 1
Transitive Closure...
We have a recursive relationship between Li ,j(k + 1) and some
“smaller” expressions L...(k).
Li ,j(k + 1) = Li ,j(k) +
(
Li ,k+1(k)Lk+1,k+1(k)
∗Lk+1,j(k)
)
Exercise: Transitive Closure
Current State Symbol New State
q1 0 q2
q1 1 q1
q1 2 q3
q2 1 q1
q2 0 q4
q2 2 q4
q3 0 q1
q3 1 q1
q3 2 q3
q4 0 q4
q4 1 q4
q4 2 q4
Compute L2,3(1).
ConcepTest
Current State Symbol New State
q1 0 q2
q1 1 q1
q1 2 q3
q2 1 q1
q2 0 q4
q2 2 q4
q3 0 q1
q3 1 q1
q3 2 q3
q4 0 q4
q4 1 q4
q4 2 q4
What is L2,4(1)?
A. {}
B. 0
C. ϵ
D. 0 + 2
ConcepTest
We have a DFA with states q1, q2, q3, q4. The start state is q1 and
the accepting states are {q1, q3}. Which of these is the regular
expression for the DFA?
A. L1,4(4)
B. L1,3(4)
C. L1,3(3)
D. None of the above