程序代写代做代考 Java decision tree algorithm flex COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 5 – INTERVIEW&CODEHELP

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

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

0 0

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

B C D

E F

1 1

ε
ε

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:

▶ From A, with a 1:

▶ From B, with ε:

▶ 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

B C D

E F

1 1

ε
ε

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:

▶ From B, with ε:

▶ 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

B C D

E F

1 1

ε
ε

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 ε:

▶ 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

B C D

E F

1 1

ε
ε

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

B C D

E F

1 1

ε
ε

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

B C D

E F

1 1

ε
ε

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

B C D

E F

1 1

ε
ε

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 1 – – – –

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

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)

B C D

E F

1 1

ε
ε

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

then r ∈ E (q)

B C D

E F

1 1

ε
ε

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

then r ∈ E (q)

B C D

E F

1 1

ε
ε

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

then r ∈ E (q)

B C D

E F

1 1

ε
ε

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

then r ∈ E (q)

B C D

E F

1 1

ε
ε

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, ε

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, ε

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, ε

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, ε

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, ε

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, ε

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, ε

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, ε

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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, ε

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

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

31/67

Outline NFA DFA ⇔ NFA Minimal DFA Regular Languages Regular Expressions Review

The table of state non-equivalences
A – – – – –
B

– – – –
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

– – –
D x

– –
E

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.

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

– – –
D 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

– –
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

– –
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.

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

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}:

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

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

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}

A,C A,D

B ,C B ,D

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

▶ 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}

A,C A,D

B ,C B ,D

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}

A,C A,D

B ,C B ,D

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

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

程序代写代做代考 Java decision tree algorithm flex COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 5

Published by admin

Leave a Reply Cancel reply