COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 5
COMP2022: Formal Languages and Logic
2018, Semester 2, Week 5
Joseph Godbehere
30th August, 2018
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or
on behalf of the University of Sydney pursuant to part VB of the
Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright
under the Act. Any further copying or communication of this
material by you may be subject of copyright protect under the Act.
Do not remove this notice.
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA)
▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties
▶ Regular Expressions (introduction)
3/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Non deterministic Finite Automata (NFA)
DFA
▶ has exactly one transition per input from each state
▶ no choice in the computation =⇒ deterministic
NFA
▶ can have any number of transitions per input from each state
▶ so some steps of the computation might be non-deterministic
▶ can also have ε-transitions
▶ i.e. transitions which the automaton can follow without
scanning any input
4/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Non-determinism
▶ As we scan through a string, the NFA can be in many states
at the same time
▶ Transitions from a state given an input symbol is to a set of
states (0, 1, 2 or more states)
▶ The string is accepted if at least one sequence of states leads
to a final state
▶ i.e. if we are in at least one accept state, after reading all the
input
▶ Parallel computation
5/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
NFA accepting strings over {0, 1} containing substring “000”
q0 q1 q2 q3
0,1
0 0 0
0,1
The corresponding DFA would be
q0 q1 q2 q3
1
0 0
1
0
1
0,1
6/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA with ε-Transitions
▶ ε-transitions do not consume any input
▶ Remember that ε is the empty string
7/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0:
B
▶ From A, with a 1:
E
▶ From B, with ε:
D
▶ From E, with ε:
B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1:
E
▶ From B, with ε:
D
▶ From E, with ε:
B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1: E
▶ From B, with ε:
D
▶ From E, with ε:
B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1: E
▶ From B, with ε: D
▶ From E, with ε:
B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1: E
▶ From B, with ε: D
▶ From E, with ε: B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1: E
▶ From B, with ε: D
▶ From E, with ε: B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
So from A with 0, we can potentially
also reach D without needing to
scan more input.
(Epsilon closure (later in the
lecture))
▶ From A, with a 0: B
▶ From A, with a 1: E
▶ From B, with ε: D
▶ From E, with ε: B and C
0 1 ε
A {E} {B} ∅
B ∅ {C} {D}
C ∅ {D} ∅
D ∅ ∅ ∅
E {F} ∅ {B ,C}
F {D} ∅ ∅
8/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Formal definition of NFA
Definition: A non-deterministic finite automaton is a 5-tuple
▶ (Q ,Σ, δ, q0,F ) where:
▶ Q is a finite set called the states,
▶ Σ is a finite set called the alphabet,
▶ δ : Q × Σε → P(Q) is the transition function*,
▶ q0 is the start state, and
▶ F ⊆ Q is the set of accept states.
*Recall:
▶ if A = {a, b, c} then
P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
▶ abε = aεb = εab = ab
▶ Σε = Σ ∪ {ε}
9/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Transition function for NFA
δ : Q × Σε → P(Q)
▶ δ(q , a) is a set of states which is the union of all the states
which can be reached from q on a.
▶ This could be the empty set ∅
▶ Note: when following epsilon transitions, you can also remain
in the same state (as if q ∈ δ(q , ε) for all q ∈ Q)
10/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
q1 q2 q3 q4
0, 1
0 0, ε 1
0, 1
▶ Q = {q1, q2, q3, q4}
▶ Σ = ?
{0, 1}
▶ The start state is q1
▶ The set of accept states
is {q4}
δ : Q × Σε → P(Q) is given by:
0 1 ε
q1 {q1, q2} {q1} ∅
q2 {q3} ∅ {q3}
q3 ∅ {q4} ∅
q4 {q4} {q4} ∅
Some strings where N reaches the accept state: 01, 0000001
11/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
q1 q2 q3 q4
0, 1
0 0, ε 1
0, 1
▶ Q = {q1, q2, q3, q4}
▶ Σ =
?
{0, 1}
▶ The start state is q1
▶ The set of accept states
is {q4}
δ : Q × Σε → P(Q) is given by:
0 1 ε
q1 {q1, q2} {q1} ∅
q2 {q3} ∅ {q3}
q3 ∅ {q4} ∅
q4 {q4} {q4} ∅
Some strings where N reaches the accept state: 01, 0000001
11/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA computation : Parallelism
q1 q2 q3 q4
0, 1
0 0, ε 1
0, 1
Several choices that exist can be seen as parallel computation or as
a tree of possibilities
Read 1 – – – –
Read 0 – – – –
Read 0 – – – –
Read 1 – – – –
q1
q1
q2q1 q3
q2 q3 q3q1
q1 q4 q4
12/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Language of an NFA
▶ A string w is accepted by an NFA if at least one sequence of
transitions starting from q0 on input w leads to an accept
state
▶ i.e. if we are in at least one accept state, after reading all the
input
▶ The language recognised by an NFA (i.e. the set of strings it
accepts) is called regular
13/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (1)
L1: Strings over {a, b, c} ending with an a
q1 q2
a, b, c
a
14/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (2)
L2: Strings over {a, b, c} composed of at least one repetition of
the substring ab
q1 q2 q3
a b
ε
15/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of NFA (3)
L3: Strings over {0, 1} with a 1 in the third last position
q1 q2 q3 q4
0, 1
1 0, 1 0, 1
16/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA)
▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties
▶ Regular Expressions (introduction)
17/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Equivalence of NFAs and DFAs
▶ DFA: exactly one transition per input from each state
▶ NFA: zero, one or several possible transitions, ε-transitions
▶ =⇒ any DFA is a NFA (NFA more general)
But are there languages that are recognised by some NFA but not
by a DFA?
No. If a language is recognised by a NFA then we can always
devise a DFA which recognises it.
Theorem: Every NFA has an equivalent DFA
18/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular languages and finite automata
Theorem (Kleene 56):
The class of regular languages is exactly the same as the class of
languages accepted by DFAs
Theorem (Rabin & Scott 59):
The class of regular languages is exactly the same as the class of
languages accepted by NFAs
=⇒ Any regular language must be accepted by at least one DFA
and at least one NFA
Can we transform NFAs into DFAs?
19/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Transforming a NFA into a DFA: intro
Key idea: Read the NFA as if it was a DFA and keep in memory
the possible set of states it could be in for each given input (i.e.
similar to the levels of the decision tree example.)
Each state of the new DFA is a subset of the NFA states (subset
construction)
When we transition from a state X , with a given input symbol i ,
we must also consider all the ways in which we could follow epsilon
transitions before and after reading i
▶ i.e. We transition to the set of states reachable via paths
using any number of ε transitions before and/or after i
20/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q , denoted E (q), is the set of all
states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E (q)
▶ If p ∈ E (q) and there is an ε-transition from p to r ,
then r ∈ E (q)
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
Example:
▶ E (A) =
{A}
▶ E (B) =
{B ,D}
▶ E (E ) =
{B ,C ,D ,E}
21/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q , denoted E (q), is the set of all
states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E (q)
▶ If p ∈ E (q) and there is an ε-transition from p to r ,
then r ∈ E (q)
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
Example:
▶ E (A) =
{A}
▶ E (B) =
{B ,D}
▶ E (E ) =
{B ,C ,D ,E}
21/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q , denoted E (q), is the set of all
states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E (q)
▶ If p ∈ E (q) and there is an ε-transition from p to r ,
then r ∈ E (q)
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
Example:
▶ E (A) = {A}
▶ E (B) =
{B ,D}
▶ E (E ) =
{B ,C ,D ,E}
21/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q , denoted E (q), is the set of all
states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E (q)
▶ If p ∈ E (q) and there is an ε-transition from p to r ,
then r ∈ E (q)
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
Example:
▶ E (A) = {A}
▶ E (B) = {B ,D}
▶ E (E ) =
{B ,C ,D ,E}
21/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure
The Epsilon-closure of a state q , denoted E (q), is the set of all
states which can be reached from q by 0 or more ε-transitions
▶ q ∈ E (q)
▶ If p ∈ E (q) and there is an ε-transition from p to r ,
then r ∈ E (q)
A
B C D
E F
0
1
ε
1 1
ε
ε
0
0
Example:
▶ E (A) = {A}
▶ E (B) = {B ,D}
▶ E (E ) = {B ,C ,D ,E}
21/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Epsilon-Closure for sets
The Epsilon-closure of a set of states S , denoted E (S ), is the
union of the Epsilon-closure of each state.
E (S ∪ T ) = E (S ) ∪ E (T )
22/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) =
{q1, q2}
E ({q2}) =
{q2}
E ({q3}) =
{q2, q3}
E ({q4}) =
{q2, q3, q4, q5}
E ({q5}) =
{q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) =
{q2}
E ({q3}) =
{q2, q3}
E ({q4}) =
{q2, q3, q4, q5}
E ({q5}) =
{q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) =
{q2, q3}
E ({q4}) =
{q2, q3, q4, q5}
E ({q5}) =
{q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) = {q2, q3}
E ({q4}) =
{q2, q3, q4, q5}
E ({q5}) =
{q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) = {q2, q3}
E ({q4}) = {q2, q3, q4, q5}
E ({q5}) =
{q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) = {q2, q3}
E ({q4}) = {q2, q3, q4, q5}
E ({q5}) = {q5}
E ({q1, q3, q5}) =
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) = {q2, q3}
E ({q4}) = {q2, q3, q4, q5}
E ({q5}) = {q5}
E ({q1, q3, q5})
=
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
=
{q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Constructing epsilon-closures
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
a b ε
q1 ∅ ∅ {q2}
q2 {q3, q4} ∅ ∅
q3 ∅ {q4} {q2}
q4 {q5} ∅ {q3, q5}
q5 ∅ ∅ ∅
E ({q1}) = {q1, q2}
E ({q2}) = {q2}
E ({q3}) = {q2, q3}
E ({q4}) = {q2, q3, q4, q5}
E ({q5}) = {q5}
E ({q1, q3, q5})
=
= E ({q1}) ∪ E ({q3}) ∪ E ({q5})
= {q1, q2, q3, q5}
23/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA to DFA algorithm
We want to convert a NFA N = (Q ,Σ, δ, q0,F ) into an equivalent
DFA M = (Q ′,Σ, δ′, q ′0,F ′) which recognises L(N )
▶ Q ′ ⊆ P(Q)
▶ Σ does not change
▶ δ′(R, a) = ∪r∈RE (δ(r , a))
▶ q ′0 = E (q0)
▶ F ′ = {R ∈ Q ′|R contains an accept state of N }
24/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
NFA to DFA algorithm
We want to convert a NFA N = (Q ,Σ, δ, q0,F ) into an equivalent
DFA M = (Q ′,Σ, δ′, q ′0,F ′) which recognises L(N )
Algorithm
1. DFA start state is E (q), where q is the NFA start state
2. If R ⊆ P(Q) is a DFA state and a ∈ Σ then construct the
following DFA state as a DFA table entry in either 2 ways:
▶ δ′(R, a) = E (∪r∈Rδ(r , a)) closure of union
▶ δ′(R, a) = ∪r∈RE (δ(r , a)) union of closures
3. A DFA state is accepting if any of its elements are an NFA
accept state.
25/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) =
{q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2}
{q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5}
∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5}
∅
{q2, q3, q4, q5}
{q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5}
{q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5}
{q2, q3, q4, q5} {q2, q3, q4, q5}
∅
∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5}
{q2, q3, q4, q5}
∅
∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅
∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4 q5
ε a
a
ε
b
ε
a, ε
Transition table:
A
B
C
a b
E (start) = {q1, q2} {q2, q3, q4, q5} ∅
{q2, q3, q4, q5} {q2, q3, q4, q5} {q2, q3, q4, q5}
∅ ∅ ∅
Resulting DFA:
A B C
a
b
a, b a, b
26/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) =
{q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2}
{q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3}
{q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3}
{q1, q2}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3}
{q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3}
{q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4}
{q1, q2, q4}
{q1, q2, q3, q4}
{q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4}
{q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4}
{q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
From NFA to DFA: example
q1 q2 q3 q4
ε
a, b
a b
a, b
Transition table:
A
B
C
D
a b
E (start) = {q1, q2} {q1, q2, q3} {q1, q2}
{q1, q2, q3} {q1, q2, q3} {q1, q2, q4}
{q1, q2, q4} {q1, q2, q3, q4} {q1, q2, q4}
{q1, q2, q3, q4} {q1, q2, q3, q4} {q1, q2, q4}
27/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA)
▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties
▶ Regular Expressions (introduction)
28/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Minimisation of DFA (idea)
Every DFA has a unique equivalent minimal DFA
Definition: Two states s and t are equivalent if: for any string, the
path from s leads to an accepting state if and only if the path
from t does.
To reduce an automaton, find all non-equivalent states:
1. If s is accepting and t non accepting, then they are not
equivalent
2. If, with input x , there is a transition from s to s ′ and from t
to to t ′ and we know that s ′ and t ′ are not equivalent, then s
and t are not equivalent
Then merge equivalent states.
29/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Minimisation of DFA: Table-filling Algorithm
1. Examine all pairs of states and find all pairs s,t that are NOT
equivalent, ie satisfying either of:
1.1 s is accepting and t is not or vice versa
1.2 with the same input x , s goes to a state s ′ and t to a state t ′
and you have already proven that s ′ and t ′ are NOT equivalent
2. When no further non-equivalence can be proven, then the
remaining pairs can be merged respectively into one state.
Theorems:
1. If two states are not distinguished by the table-filling
algorithm, then the states are equivalent
2. The equivalence of states is transitive
30/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
A B C
D E
0
1
0
1
0
1
0
1
0
1
31/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B
x
– – – –
C
x x
– – –
D
x x
– –
E
x x x x
–
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x
x
– – –
D x
x
– –
E
x
x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x
x
– – –
D x
x
– –
E x x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x x – – –
D x
x
– –
E x x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x x – – –
D x
x
– –
E x x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x x – – –
D x x – –
E x x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
The table of state non-equivalences
A – – – – –
B x – – – –
C x x – – –
D x x – –
E x x x x –
A B C D E
1. Cross out all the pairs of accept/non-accept states. A, E are
non-accepting and all the others are.
2. Look at each remaining pair.
▶ δ(A, 0) = A and δ(E , 0) = C , but A ̸≡ C , therefore A ̸≡ E
▶ δ(B , 0) = D and δ(C , 0) = E , but D ̸≡ E , therefore B ̸≡ C
▶ We can’t find a reason to claim B ̸≡ D yet
▶ δ(C , 0) = E and δ(D , 0) = B , and E ̸≡ B , therefore C ̸≡ D
3. Repeat step 2 until no changes are found
32/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Merging equivalent states
Theorem: If two states are not distinguished by the table-filling
algorithm, then that pair of states are equivalent.
We can merge together equivalent states. The minimal DFA for
the example becomes:
A BD C
E
0
1
0
1
0
1
0
1
33/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Resulting DFA
▶ is minimal
▶ is unique
34/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA)
▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties
▶ Regular Expressions (introduction)
35/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Revision
Definition:
A language is regular if and only if there exists a finite automaton
which recognises it.
Minimal examples:
▶ ∅ is a regular language
▶ {ε} is a regular language
▶ For all a ∈ Σ, the set {a} is a regular language
Think about how to make a DFA for each of these languages
36/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Closure properties of Regular languages
Let L1 and L2 be regular languages.
The regular operations are defined as follows:
▶ Union: L1 ∪ L2 = {w |w ∈ L1 or w ∈ L2}
▶ Concatenation: L1L2 = {w1w2|w1 ∈ L1 and w2 ∈ L2}
▶ Star: L∗ = {w1w2…wk |k ≥ 0 and wi ∈ L for i = 1, …, k}
Theorems
▶ The union of two regular languages is regular
▶ The concatenation of two regular languages is regular
▶ The star closure of a regular language is regular
37/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union of two regular languages
If L1 and L2 are regular, then finite automata M1 and M2 exist
which recognise them. we can construct an automaton M which
recognises L1 ∪ L2 = {w |w ∈ L1 or w ∈ L2}:
q0
q1
q2
M1
M2
ε
ε
38/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union of two regular languages
Let M1 = (Q1,Σ, δ1, q1,F1), M2 = (Q2,Σ, δ2, q2,F2)
Let M = (Q ,Σ, δ, q0,F ) where:
▶ Q = {q0} ∪Q1 ∪Q2
▶ q0 is the new start state
▶ Transition function δ defined 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 ̸= ε
▶ Accepting set F = F1 ∪ F2
M accepts if and only if M1 or M2 does
i.e. L(M ) = {w |w ∈ L1 or w ∈ L2} = L1 ∪ L2
39/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Concatenation of two regular languages
If L1 and L2 are regular, then finite automata M1 and M2 exist
which recognise them.
we can construct an automaton M which recognises
L1L2 = {w1w2|w1 ∈ L1 and w2 ∈ L2}:
q1 ∈ F1
∈ F1
q2
M1 M2
ε
ε
Note that the accept states of M1 are not accept states in M
40/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Concatenation of two regular languages
Let M1 = (Q1,Σ, δ1, q1,F1), M2 = (Q2,Σ, δ2, q2,F2)
Let M = (Q ,Σ, δ, q0,F ) where:
▶ Q = Q1 ∪Q2
▶ q1 is start state (same as M1)
▶ Transition function δ defined for any q ∈ Q and any a ∈ Σε
δ(q , a) =
δ1(q , a) if q ∈ Q1 and q ̸∈ F1
δ1(q , a) if q ∈ F1 and a ̸= ε
δ1(q , a) ∪ {q2} if q ∈ F1 and a = ε
δ2(q , a) if q ∈ Q2
▶ Accepting set F = F2 (same as M2)
L(M ) = {w1w2|w1 ∈ L1 and w2 ∈ L2} = L1L2
41/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Star closure of a regular language
If L is regular, then a finite automaton M1 exists which recognises
it.
we can construct an automaton M which recognises
L∗ = {w1w2…wk |k ≥ 0 and wi ∈ L for i = 1, …, k}:
q0 q1
M1
ε
ε
ε
e.g. if L = {a, b} then this automaton recognises
{ε, a, b, aa, ab, bb, aaa, …} = L∗
42/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Star closure of a regular language
Let M1 = (Q1,Σ, δ1, q1,F1)
Let M = (Q ,Σ, δ, q0,F ) where:
▶ Q = Q1 ∪ {q0}
▶ q0 is the new start state
▶ Transition function δ defined for any q ∈ Q and any a ∈ Σε
δ(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 ̸= ε
▶ Accepting set F = F1 ∪ {q0}
L(M ) = {w1w2…wk |k ≥ 0 and wi ∈ L for i = 1, …, k} = L∗
43/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example
Construct an NFA recognising the set of strings containing the
pattern aaab or the strings composed of 0 or more sequences of ab
44/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example from construction to minimal DFA
Let Σ = {0, 1}
Let L1 be the language of strings which do not contain consecutive
0’s
Let L2 be the language of strings ending with 0
45/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Complement of a regular language
The complement of a regular language is regular
The complement of a language L is {x |x ̸∈ L}
Example:
Let L1 = {x |x contains an odd number of a’s}
Then the complement of L1 is L2 = {x |x ̸∈ L1} = {x |x contains
an even number of a’s}
You will explore how to construct a suitable automata in this
week’s tutorial
46/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Intersection of a regular language
If L1 and L2 are regular, then L1 ∩ L2 is regular.
We can use the cross product technique to build the DFA
Example:
L1 = {x |x ∈ {a, b}∗ and x contains an odd number of a’s}
L2 = {x |x ∈ {a, b}∗ and x contains an odd number of b’s}
M1
A
B
b
a
b
a
M2
C
D
a
b
a
b
A,C A,D
B ,C B ,D
a
b
a
b
a
b
a
b
47/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Cross-product of DFAs
Let M1 = (Q1,Σ, δ1, q1,F1), M2 = (Q2,Σ, δ2, q2,F2) be two DFA
Let M = (Q ,Σ, δ1, q0,F ) where:
▶ Q = Q1 ×Q2 (i.e. all ordered pairs (u, v) such that u ∈ Q1
and v ∈ Q2)
▶ The start state (q1, q2) is the pair of start states from Q1 and
Q2
▶ The transition function δ is defined as:
δ((u, v), x ) = (δ1(u, x ), δ2(v , x ))
▶ Accepting set F = {(u, v)|u ∈ F1 and v ∈ F2}
Note that M is also deterministic
48/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Example Cross-product for Intersection
Example:
L1 = {x |x ∈ {a, b}∗ and x contains an odd number of a’s}
L2 = {x |x ∈ {a, b}∗ and x contains an odd number of b’s}
M1
A
B
b
a
b
a
M2
C
D
a
b
a
b
A,C A,D
B ,C B ,D
a
b
a
b
a
b
a
b
49/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Cross-product can be used for Union
Example:
L1 = {x |x ∈ {a, b}∗ and x contains an odd number of a’s}
L2 = {x |x ∈ {a, b}∗ and x contains an odd number of b’s}
M1
A
B
b
a
b
a
M2
C
D
a
b
a
b
A,C A,D
B ,C B ,D
a
b
a
b
a
b
a
b
50/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Outline
▶ Non-Deterministic Finite Automata (NFA)
▶ Non-determinism
▶ ε-transitions
▶ Equivalence of NFA and DFA
▶ Minimal DFA
▶ Regular Languages and Closure properties
▶ Regular Expressions (introduction)
51/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions
In arithmetic we use operations to build up expressions, describing
numbers such as
(5 + 3)× 4 (value is 32)
4/2− 1 (value is 1)
With regular languages, we use regular operations to build up
expressions describing languages such as
(0 | 1)0⋆ (strings starting with 0 or 1, then any number of 0’s)
(ab)⋆a (any number of ab’s, followed by a)
52/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions vs Finite Automata
▶ RegEx: algebraic description of the strings in a language
▶ FA: a machine-like description
▶ RegEx serve as the input language for many systems which
process strings
▶ Search commands
▶ UNIX grep
▶ Web browsers
▶ Text editors
▶ Text formatting systems
▶ …
▶ Lexical-analyser generators (Lex, Flex, etc.)
▶ Like FA, RegEx define exactly the class of regular languages
53/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Definition of a Regular Expression (RegEx)
▶ Basic expressions and the language they describe
▶ If a is any symbol of the input alphabet, then a is a RegEx
and its language L(a) = {a}
▶ ε is a RegEx and L(ε) = {ε}
▶ ∅ is a RegEx and L(∅) = ∅
▶ Operators on RegEx. If R and S are RegEx, then
▶ Union: R | S (sometimes denoted R + S ) is a RegEx
▶ Concatenation: RS (sometimes denoted R ◦ S ) is a RegEx
▶ Star Closure: R⋆ is a RegEx
▶ Precedence of operators: ⋆, ◦, | to avoid excessive parentheses
▶ e.g. R | ST ⋆ = (R | (S (T ⋆))), similar to how
8 + 21/32 = (8 + (21/(32)))
▶ Use parentheses to change the order of operations
54/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Definition of a Regular Expression (RegEx)
▶ Basic expressions and the language they describe
▶ If a is any symbol of the input alphabet, then a is a RegEx
and its language L(a) = {a}
▶ ε is a RegEx and L(ε) = {ε}
▶ ∅ is a RegEx and L(∅) = ∅
▶ Operators on RegEx. If R and S are RegEx, then
▶ Union: R | S (sometimes denoted R + S ) is a RegEx
▶ Concatenation: RS (sometimes denoted R ◦ S ) is a RegEx
▶ Star Closure: R⋆ is a RegEx
▶ Precedence of operators: ⋆, ◦, | to avoid excessive parentheses
▶ e.g. R | ST ⋆ = (R | (S (T ⋆))), similar to how
8 + 21/32 = (8 + (21/(32)))
▶ Use parentheses to change the order of operations
54/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Definition of a Regular Expression (RegEx)
▶ Basic expressions and the language they describe
▶ If a is any symbol of the input alphabet, then a is a RegEx
and its language L(a) = {a}
▶ ε is a RegEx and L(ε) = {ε}
▶ ∅ is a RegEx and L(∅) = ∅
▶ Operators on RegEx. If R and S are RegEx, then
▶ Union: R | S (sometimes denoted R + S ) is a RegEx
▶ Concatenation: RS (sometimes denoted R ◦ S ) is a RegEx
▶ Star Closure: R⋆ is a RegEx
▶ Precedence of operators: ⋆, ◦, | to avoid excessive parentheses
▶ e.g. R | ST ⋆ = (R | (S (T ⋆))), similar to how
8 + 21/32 = (8 + (21/(32)))
▶ Use parentheses to change the order of operations
54/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Language of a Regular Expression
Let x , y be symbols from the input alphabet
L(x ) = {x}
L(ε) = {ε}
L(∅) = {∅}
L(x | y) = {x , y}
L(x ⋆) = {ε, x , xx , xxx , …}
L(xy) = {xy}
55/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) =
L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) =
L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) =
L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
=
{a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
=
{a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) =
L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
=
{a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
=
{a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Union R | S
Definition: L(R | S ) = L(R) ∪ L(S )
L(a | b) = L(a) ∪ L(b) = {a} ∪ {b} = {a, b}
L(b | a) = L(b) ∪ L(a) = {b} ∪ {a} = {a, b} = L(a | b)
L((a | b) | c) = L(a | b) ∪ L(c)
= {a, b} ∪ {c}
= {a, b, c}
L(a | (b | c)) = L(a) ∪ L(b | c)
= {a} ∪ {b, c}
= {a, b, c}
Because it is associative we can write L(a | b | c)
56/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) =
{rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) =
{rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) =
{rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
=
{rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
=
{abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) =
{rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
=
{rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
=
{abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Concatenation RS
Definition: L(RS ) = {rs | r ∈ L(R) and s ∈ L(S )}
L(ab) = {rs | r ∈ L(a) and s ∈ L(b)} = {ab}
L(ba) = {rs | r ∈ L(b) and s ∈ L(a)} = {ba}
L((ab)c) = {rs | r ∈ L(ab) and s ∈ L(c)}
= {rs | r ∈ {ab} and s ∈ {c}}
= {abc}
L(a(bc)) = {rs | r ∈ L(a) and s ∈ L(bc)}
= {rs | r ∈ {a} and s ∈ {bc}}
= {abc}
Because it is associative we can write L(abc)
57/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) =
{rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) =
L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
=
{rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) =
L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
=
{rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) =
L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
=
{ac, bc}
L((ab) | c) =
L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) =
L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) = L(ab) ∪ L(c)
=
{rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) = L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
=
{rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) = L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
=
{ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Union and Concatenation
L((a | b)c) = {rs | r ∈ L(a | b) and s ∈ L(c)}
= {rs | r ∈ ({a} ∪ {b}) and s ∈ {c}}
= {rs | r ∈ {a, b} and s ∈ {c}}
= {ac, bc}
L((ab) | c) = L(ab) ∪ L(c)
= {rs | r ∈ L(a) and s ∈ L(b)} ∪ L(c)
= {rs | r ∈ {a} and s ∈ {b}} ∪ {c}
= {ab} ∪ {c}
= {ab, c}
58/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …}
L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) =
{ε} ∪ L(∅) ∪ … = {ε}
L(a | bc⋆) = {a, b, bc, bcc, bccc, …}
L(a | (bc)⋆) = {a, ε, bc, bcbc, bcbcbc, …}
L((a | b)c⋆) = {a, b, ac, bc, acc, bcc, accc, bccc, …}
59/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …}
L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) = {ε} ∪ L(∅) ∪ … = {ε}
L(a | bc⋆) =
{a, b, bc, bcc, bccc, …}
L(a | (bc)⋆) = {a, ε, bc, bcbc, bcbcbc, …}
L((a | b)c⋆) = {a, b, ac, bc, acc, bcc, accc, bccc, …}
59/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …}
L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) = {ε} ∪ L(∅) ∪ … = {ε}
L(a | bc⋆) = {a, b, bc, bcc, bccc, …}
L(a | (bc)⋆) =
{a, ε, bc, bcbc, bcbcbc, …}
L((a | b)c⋆) = {a, b, ac, bc, acc, bcc, accc, bccc, …}
59/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …}
L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) = {ε} ∪ L(∅) ∪ … = {ε}
L(a | bc⋆) = {a, b, bc, bcc, bccc, …}
L(a | (bc)⋆) = {a, ε, bc, bcbc, bcbcbc, …}
L((a | b)c⋆) =
{a, b, ac, bc, acc, bcc, accc, bccc, …}
59/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Operators on RegEx: Star closure R⋆
R⋆ means 0 or more occurrences of R
L(R⋆) = {ε} ∪ L(R) ∪ L(RR) ∪ L(RRR) ∪ …
L(0⋆) = {ε, 0, 00, 000, …}
L((01)⋆) = {ε, 01, 0101, 010101, …}
L(∅⋆) = {ε} ∪ L(∅) ∪ … = {ε}
L(a | bc⋆) = {a, b, bc, bcc, bccc, …}
L(a | (bc)⋆) = {a, ε, bc, bcbc, bcbcbc, …}
L((a | b)c⋆) = {a, b, ac, bc, acc, bcc, accc, bccc, …}
59/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Union properties:
▶ R | S = S | R (commutative)
▶ R | ∅ = ∅ | R = R
▶ R | R = R
▶ (R | S ) | T = R | (S | T ) (associative)
▶ Concatenation properties:
▶ R∅ = ∅R = ∅
▶ Rε = εR = R
▶ (RS )T = R(ST ) (associative)
▶ Union and concatenation are distributive when combined:
▶ R(S | T ) = RS | RT
▶ (S | T )R = SR | TR
60/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Union properties:
▶ R | S = S | R (commutative)
▶ R | ∅ = ∅ | R = R
▶ R | R = R
▶ (R | S ) | T = R | (S | T ) (associative)
▶ Concatenation properties:
▶ R∅ = ∅R = ∅
▶ Rε = εR = R
▶ (RS )T = R(ST ) (associative)
▶ Union and concatenation are distributive when combined:
▶ R(S | T ) = RS | RT
▶ (S | T )R = SR | TR
60/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Union properties:
▶ R | S = S | R (commutative)
▶ R | ∅ = ∅ | R = R
▶ R | R = R
▶ (R | S ) | T = R | (S | T ) (associative)
▶ Concatenation properties:
▶ R∅ = ∅R = ∅
▶ Rε = εR = R
▶ (RS )T = R(ST ) (associative)
▶ Union and concatenation are distributive when combined:
▶ R(S | T ) = RS | RT
▶ (S | T )R = SR | TR
60/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Some properties of RegEx
Let R,S ,T be regular expressions
▶ Star Closure properties:
▶ ∅⋆ = ε⋆ = ε
▶ R⋆ = R⋆R⋆ = (R⋆)⋆ = R | R⋆
▶ R⋆ = ε | R⋆ = (ε | R)⋆ = (ε | R)R⋆ = ε | RR⋆
▶ RR⋆ = R⋆R
▶ (R | S )⋆ = (R⋆ | S⋆)⋆ = (R⋆S⋆)⋆ = (R⋆S )⋆R⋆ = R⋆(SR⋆)⋆
▶ R(SR)⋆ = (RS )⋆R
▶ (R⋆S )⋆ = ε | (R | S )⋆S
▶ (RS⋆)⋆ = ε | R(R | S )⋆
61/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c
(a | b | c)⋆
▶ Strings over {0, 1} which end with 01
(0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
(letter | $ | _)(letter | digit | $ | _)⋆
62/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c
(a | b | c)⋆
▶ Strings over {0, 1} which end with 01
(0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
(letter | $ | _)(letter | digit | $ | _)⋆
62/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c
(a | b | c)⋆
▶ Strings over {0, 1} which end with 01
(0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
(letter | $ | _)(letter | digit | $ | _)⋆
62/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c
(a | b | c)⋆
▶ Strings over {0, 1} which end with 01
(0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
(letter | $ | _)(letter | digit | $ | _)⋆
62/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ All possible strings which can be formed with a, b, or c
(a | b | c)⋆
▶ Strings over {0, 1} which end with 01
(0 | 1)⋆01
▶ Traffic lights?
(red | red ◦ amber | amber | green)
▶ Identifiers for Java programs?
(letter | $ | _)(letter | digit | $ | _)⋆
62/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a, b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s
starting and ending with a, or a single a or b
▶ a⋆∅ represents
The empty language, ∅
63/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a, b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s
starting and ending with a, or a single a or b
▶ a⋆∅ represents
The empty language, ∅
63/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a, b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s
starting and ending with a, or a single a or b
▶ a⋆∅ represents
The empty language, ∅
63/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a, b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s
starting and ending with a, or a single a or b
▶ a⋆∅ represents
The empty language, ∅
63/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Examples of RegEx
▶ a⋆ba⋆ represents
Strings over {a, b} with exactly one b
▶ ((a | b)(a | b))⋆ represents
Strings over {a, b} with even length
▶ ab⋆a | ba⋆b | a | b represents
Strings of a’s starting and ending with b, or strings of b’s
starting and ending with a, or a single a or b
▶ a⋆∅ represents
The empty language, ∅
63/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Equivalence of RegEx and FA
Theorem:
A language is regular if and only if a regular expression describes it.
Proof:
Show the equivalence of RegEx and FA (RegEx ⇔ FA)
1. RegEx ⇒ FA:
Show that for each RegEx, there exists an NFA which
recognises the same language
2. FA ⇒ RegEx:
Show that for each NFA, there exists a RegEx which
recognises the same language
Next week: proof
64/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Equivalence of RegEx and FA
Theorem:
A language is regular if and only if a regular expression describes it.
Proof:
Show the equivalence of RegEx and FA (RegEx ⇔ FA)
1. RegEx ⇒ FA:
Show that for each RegEx, there exists an NFA which
recognises the same language
2. FA ⇒ RegEx:
Show that for each NFA, there exists a RegEx which
recognises the same language
Next week: proof
64/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Application: pattern matching
▶ Provides a technique for finding occurrences of patterns in
text (e.g. web/document searching)
▶ Some of the best known algorithms are based on Finite
Automata!
▶ Constructing a NFA to recognise the strings containing the
pattern is trivial.
▶ Then we convert the NFA to DFA, then minimal DFA, so the
pattern can be matched efficiently
65/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
DFAs and NFAs
▶ NFAs and DFAs define the class of regular languages
▶ Each NFA can be transformed into a unique minimal DFA
▶ NFAs are often more intuitive to build and easier to
understand
▶ DFA – especially minimal DFA – are more efficient to compute
▶ despite the fact they often have far more states than the NFA
▶ Regular languages are closed under the union, concatenation,
star closure, intersection, and complement operations
▶ We use these to build the NFA, before converting to a minimal
DFA
66/67
Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review
Regular Expressions
▶ What they are and how to use them
▶ Regular operations
▶ Equivalence with DFA/NFA
67/67
Outline
outline
NFA
NFA
DFA NFA
outline
Minimal DFA
outline
minimisation
Regular Languages
outline
union
concatenation
star closure
examples
complement
intersection / cross product
Regular Expressions
outline
Regular Expressions
operators
examples
FA RegEx
Review
review