COMP2022|2922
Models of Computation
Lesson 6a: Nondeterministic finite automata
Presented by
Sasha Rubin
School of Computer Science
Theorem
The regular languages are closed under concatenation. That is, if A and B are regular, then A ◦ B is regular.
Idea:
– Let MA be a DFA recognising A, let MB be a DFA
recognising B.
– WewanttobuildaDFAM forA◦B.
– One way would be for M to simulate MA, and at some point, as long as the state of MA is an accepting state, “guess” that it is time to switch, and simulate MB on the remaining input.
Question. How to we capture this “guess”?
1/38
We will introduce a model of computation, called a nondeterministic finite automaton (NFA), which is like a DFA except that states can have more than one outgoing transition on the same input symbol. Later we will show how DFAs can simulate NFAs.
2/38
Definition of NFA
Definition
A nondeterministic finite automaton M is a tuple (Q, Σ, δ, q0 , F ) the same as a DFA except the transition function is
′ a′1 δ:Q×(Σ∪{ε})→P(Q). Ifq ∈δ(q,a)wewriteq−→q.
1Recall: P(Q) is the set of subsets of Q. So P({q1,q2,q3}) has 8 elements.
3/38
Definition of NFA
The NFA M accepts w if there is a path y0 y1 ym
q0 −→q1 −→q2…−→qm inM suchthatw=y1y2···ym andqm ∈F.
That is: an NFA M describes the language L(M) of all strings that label paths from the start state to an accepting state.
4/38
Language described by NFAs
Examples
Let Σ = {a, b}. Draw an NFA for the languages consisting of the set of strings who last letter is an a (also, draw a DFA, for comparison).
5/38
Comparing NFAs and DFAs
1. In a DFA, every input has exactly one run. The input string is accepted if this run is accepting.
2. In an NFA, an input may have zero, one, or more runs. The input string is accepted if at least one of its runs is accepting.
3. For every DFA M there is an NFA N such that L(M) = L(N).
– GivenDFAM=(Q,Σ,δ,q0,F)withδ:Q×Σ→Q,define the NFA N = (Q,Σ,δ′,q0,F) where δ′(q,a) = {δ(q,a)}.
– To see that L(M) = L(N) observe that the diagrams of M
and N are the same.
6/38
From Regular Expressions to DFA
Theorem
For every regular expression R there is an NFA MR such that L(R) = L(MR).
The construction is by recursion on the structure of R. The base casesareR=∅,R=ε,R=afora∈Σ. Therecursivecasesare R = R1 ◦R2,R = R1 ∪R2, and R = (R1)∗.
Base cases:
7/38
NFAs are closed under ◦ Lemma
If N1, N2 are NFAs, there is an NFA N recognising L(N1) ◦ L(N2). Construction (“Simulate N1 followed by N2”)
Given NFAs Ni = (Qi, Σ, δi, qi, Fi) construct NFA N with states Q1 ∪ Q2 as in the figure. The idea is that N guesses how to break the input into two pieces, the first accepted by N1, and the second by N2.
8/38
NFAs are closed under ◦ (reference slide) Here is the construction. From Ni = (Qi, Σ, δi, qi, Fi) construct
N = (Q1 ∪ Q2, Σ, δ, q1, F2) where
δ(q,a) q∈Q \F
1 11 δ1(q,a) q ∈ F1,a ̸= ε
δ(q, a) =
δ1(q,a)∪{q2} q∈F1,a=ε
δ 2 ( q , a ) q ∈ Q 2
9/38
NFAs are closed under ∪ Lemma
If N1, N2 are NFAs, there is an NFA N recognising L(N1) ∪ L(N2). Construction (“Simulate N1 or N2”)
Given NFAs Ni = (Qi, Σ, δi, qi, Fi) construct NFA N with states Q1 ∪ Q2 ∪ {q0} as in the figure. The idea is that N guesses which of N1 or N2 to simulate.
10/38
NFAs are closed under ∪ (reference slide) Here is the construction. From Ni = (Qi, Σ, δi, qi, Fi) construct
N = (Q1 ∪ Q2 ∪ {q0}, Σ, δ, q0, F1 ∪ F2) where δ(q,a) q∈Q
δ(q, a) =
1
δ 2 ( q , a )
{q1,q2} ∅
1 q ∈ Q 2
q = q0,a = ε q = q 0 , a ̸ = ε
11/38
NFAs are closed under ∗ Lemma
If N1 is an NFA, there is an NFA N recognising L(N1)∗. Construction (“Simulate N and go back to the initial
state”)
Given NFAs N1 = (Q1, Σ, δ1, q1, F1) construct NFA N with states Q ∪ {q0} as in the figure. The idea is that N guesses how to break the input into pieces, each of which is accepted by N1.
12/38
NFAs are closed under ∗ (reference slide) Here is the construction. From N1 = (Q1, Σ, δ1, q1, F1) construct
N = (Q1 ∪ {q0}, Σ, δ, q0, F1 ∪ {q0}) where
δ (q,a) (q∈Q \F )or(q∈F ,a̸=ε)
1 111 δ1(q,a)∪{q1} q∈F1,a=ε
δ(q, a) =
{q1} q = q0,a = ε
∅ q = q 0 , a ̸ = ε
13/38
From RE to NFA: example
Convert the regular expression ((a ∪ b)∗ ◦ a) to an NFA (using the construction just given).
14/38
COMP2022|2922
Models of Computation
Lesson 6b: NFAs, DFAs, REs have the same expressive power
Presented by
Sasha Rubin
School of Computer Science
Where are we going?
We are going to show that DFA, NFA and regular expressions have the same expressive power. I.e., they recognise the same languages.
1. From Regular Expressions to NFAs
2. From NFAs to NFAs without ε-transitions 3. From NFAs without ε-transitions to DFAs 4. From DFAs to Regular Expressions
15/38
From NFAs to NFAs without ε-transitions
Theorem
For every NFA N there is an NFA N′ without ε-transitions such that L(N) = L(N′).
Construction (“skip ε-transitions”) ε∗
′ ε∗a
– t∈δ(s,a)if,inN,thereisastateqsuchthats−→q−→t.
′ ε∗
– s∈F if,inN,thereisastateq∈F suchthats−→q.
The idea is that N′ skips over the ε-transitions of N.
Given NFA N = (Q,Σ,δ,q0,F) write s −→ t if there is a path from s to t labelled only by ε. Construct N′ = (Q,Σ,δ′,q0,F′) where
16/38
From NFAs to NFAs without ε-transitions Example
17/38
From NFAs without ε-transitions to DFAs
Theorem
For every NFA N without ε-transitions there is a DFA M such that L(M) = L(N).
Construction (“subset construction”)
Intuitively, M keeps track of all possible states that N can be in. Given NFA N = (Q,Σ,δ,q0,F) construct M = (Q′,Σ,δ′,{q0},F′) where
– Q′ =P(Q),i.e.,everysubsetX⊆QisastateofQ′, – for X ⊆ Q, δ′(X,a) = ∪q∈Xδ(q,a),
– F ′ = {X ⊆ Q : X ∩ F ̸= ∅}.
18/38
From NFAs without ε-transitions to DFAs Example
19/38
From DFAs to Regular Expressions
Theorem
For every DFA M there is a regular expression R such that L(M) = L(R).
Idea:
1. We convert M into a generalised nondeterministic finite automaton (GNFA) which is like an NFA except that it can have regular expressions label the transitions.
2. We successively remove states from the automaton, until there is just one transition (from the start state to the final state).
3. We return the regular expression on this last transition.
20/38
GNFAs
A GNFA N accepts w if there is a path
R0 R1 Rm
q 0 − −→ q 1 − −→ q 2 . . . −−→ q m
in M such that w matches the regular expression R1R2 · · · Rm and
qm ∈F. Example
21/38
From DFAs to Regular Expressions
Generalised NFAs. We make sure that:
1. the initial state has no incoming edges.
2. there is one final state, and it has no outgoing edges.
3. there are edges from every state (that is not final) to every state (that is not initial).
We show how to translate DFAs into GNFAs, and then successively remove states from the GNFA until there is just a single edge left.
22/38
From DFAs to GNFAs
For every DFA M there is a GNFA N such that L(M) = L(N).
1. Add an initial state and ε-transition to the old intial state.
2. Add a final state and ε-transitions to it from all the old final states.
3. Add transitions for every pair of states (except from the new final to the new initial).
23/38
Removing states from GNFAs
For every GNFA N with > 2 states there is a GNFA N′ with one less state such that L(N) = L(N′).
1. Pick a state q to eliminate.
2. For every pair of remaining states (s, t), replace the label from
s to t by the regular expression
(Rs,t ∪(Rs,q ◦(Rq,q)∗ ◦ Rq,t)).
where Rx,y is the regular expression labeling the transition from state x to state y.
24/38
Removing states from GNFAs
Example
25/38
Summary
1. The following models of computation describe the same languages: DFAs, NFAs, Regular Expressions.
2. The regular languages are closed under the Boolean operations union, intersection, complementation, as well as concatenation and Kleene star.
26/38
Decision Problems about DFAs
Input: DFA M and string w
Output: 1 if w ∈ L(M), and 0 otherwise.
Input: DFA M
Output: 1 if L(M) = ∅, and 0 otherwise.
Input: DFAs M1,M2
Output: 1 if L(M1) = L(M2), and 0 otherwise.
27/38
Emptiness problem for DFAs
Input: DFA M
Output: 1 if L(M) = ∅, and 0 otherwise.
Algorithm (“mark reachable states”)
1. Mark the states using the following recursive procedure.
1.1 Mark the initial state.
a
1.2 Ifqismarkedandp−→q(forsomea∈Σ),thenmarkp. 1.3 (Stop when no new states are marked).
2. Return 0 if a final state is marked, else return 1.
28/38
Equivalence problem for DFAs
Input: DFAs M1,M2
Output: 1 if L(M1) = L(M2), and 0 otherwise.
Algorithm
1. Form DFA M recognising
(L(M1) \ L(M2)) ∪ (L(M2) \ L(M1)).
– Note that L(M1) = L(M2) iff L(M) = ∅.
2. SowejustneedawaytocheckifL(M)=∅. Usethe algorithm for the Emptiness problem for DFAs.
29/38
Decision Problems about Regular Expressions
Input: Regular expression R and string w Output: 1 if w ∈ L(R), and 0 otherwise.
Input: Regular expressions R1, R2
Output: 1 if L(R1) = L(R2), and 0 otherwise.
30/38