COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 6
COMP2022: Formal Languages and Logic
2018, Semester 2, Week 6
Joseph Godbehere
6th September, 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 RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Outline
▶ Regular Expressions
▶ Equivalence of FA and Regular Expressions
▶ Proving if a language is, or is not, regular
3/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Outline
▶ Regular Expressions
▶ Equivalence of FA and Regular Expressions
▶ Proving if a language is, or is not, regular
4/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus 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
5/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
From RegEx to FA: atomic cases
Automaton for ∅
Automaton for ε
Automaton for x ∈ Σ
x
6/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
NFA for regular operations: Union
Let M1 and M2 be automata recognising L(R1) and L(R2)
Then an automaton M for R1 | R2 is:
q0
q1
q2
M1
M2
ε
ε
7/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
NFA for regular operations: Concatenation
Let M1 and M2 be automata recognising L(R1) and L(R2)
Then an automaton M for R1 ◦ R2 is:
q1 ∈ F1
∈ F1
q2
M1 M2
ε
ε
Reminder: the accept states of M1 are not accept states in M
8/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
NFA for regular operations: Star closure
Let M1 be an automaton recognising L(R1)
Then an automaton M for R⋆1 is:
q0 q1
M1
ε
ε
ε
9/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: a | bc⋆: from RegEx to NFA
1. Construct automata for the atomic regular expressions a, b, c
a
b
c
10/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: a | bc⋆: from RegEx to NFA
1. Construct automata for the atomic regular expressions a, b, c
2. Use the Star Closure operation to find an automaton for c⋆
ε
c
ε
11/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: a | bc⋆: from RegEx to NFA
1. Construct automata for the atomic regular expressions a, b, c
2. Use the Star Closure operation to find an automaton for c⋆
3. Use the Concatenation operation to find an automaton for bc⋆
b ε ε
c
ε
12/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: a | bc⋆: from RegEx to NFA
1. Construct automata for the atomic regular expressions a, b, c
2. Use the Star Closure operation to find an automaton for c⋆
3. Use the Concatenation operation to find an automaton for bc⋆
4. Use the Union operation to find an automaton for a|bc⋆
ε
ε
a
b ε ε
c
ε
13/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
From NFA to RegEx: Simple examples
This automaton gives the RegEx x
x
This one gives (a | b | … | Y | Z )⋆.pdf
a…z ,A…Z
. p d f
14/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
From NFA to RegEx: Simple examples
A more complex one:
0
1 0
1
0, 1
1⋆ 0 0⋆ 1 (0 | 1)⋆
1⋆00⋆1(0 | 1)⋆
15/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Concept
Algorithm to convert an NFA to a RegEx:
1. Convert the NFA to a Generalised NFA (GNFA)
▶ Only one start state, no incoming transitions
▶ Only one accept state, no outgoing transitions
▶ Transitions described by RegEx
2. Progressively eliminate all states between the start and accept
state
3. The transition between the start and the accept state is now a
regular expression describing L
16/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Generalised NFA (GNFA)
The start state qs is non-accepting and has no incoming transitions
The only accept state qa has no outgoing transitions, and qs ̸= qa
There is exactly one transition between each ordered pair of states,
labelled with a RegEx.
qs q1 q2 qa
ε
aa⋆ a | bb
ε
∅ ∅
bc
∅
bc
We do not show the ∅ transitions (why not?)
{abc, abca, abcbb, aaaaaabc} ⊆ L
17/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Generalised NFA (GNFA)
The start state qs is non-accepting and has no incoming transitions
The only accept state qa has no outgoing transitions, and qs ̸= qa
There is exactly one transition between each ordered pair of states,
labelled with a RegEx.
qs q1 q2 qa
ε
aa⋆ a | bb
ε
∅ ∅
bc
∅
bc
We do not show the ∅ transitions (why not?)
{abc, abca, abcbb, aaaaaabc} ⊆ L
17/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Converting an NFA to a GNFA
Create a new non-accepting start state qs , with a ε-transition to
the original start state.
Create a new accept state qa with ε-transitions from the original
accept states, which are no longer accepting.
Label the transitions between every ordered pair (qi , qj ) of states
from the NFA as the union of the atomic RegEx describing each
transition from qi to qj in the NFA.
q1
q2
a
b
a, b
qs q1
q2qa
ε
a
b
a | b
ε
18/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Simple example: eliminate state q1
qs q1 q2 qa
ε
a
b
a | b
ε
There is only one way to pass through q1:
qs → q1 ε
q1 → q1 any number of times a⋆
q1 → q2 b
We set the transition qs → q2 to the union of the new RegEx and
it’s old value (∅). This is εa⋆b | ∅, which simplifies to a⋆b
qs q2 qa
a⋆b
a | b
ε
19/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Simple example: eliminate state q2
qs q2 qa
a⋆b
a | b
ε
There is only one way to pass through q2:
qs → q2 a⋆b
q2 → q2 any number of times (a|b)⋆
q2 → qa ε
qs qa
a⋆b(a | b)⋆
The language of the original automaton is a⋆b(a | b)⋆
20/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
General method to eliminate state qelim
Consider each pair (qi , qj ) where qi , qj ∈ Q \ {qelim}
qi qj
qelim
R4
R1 R3
R2
Replace the transition from qi to qj with the expression
((R1)(R2)
⋆(R3) | (R4))
Note:
▶ Possibly qi = qj
▶ Recall that pairs are ordered, so we also consider (qj , qi)
▶ If there is no transition Rx , then Rx = ∅
21/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
q0 q1 q2
0
1 0
1 0
1
Convert to GNFA:
qs
q0
q1
q2
qa
ε
0 1 0
1 0
1
ε
22/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
q0 q1 q2
0
1 0
1 0
1
Convert to GNFA:
qs
q0
q1
q2
qa
ε
0 1 0
1 0
1
ε
22/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶
(qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶
(qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶
(q1, q1) : R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶
(q1, qa) : R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) :
R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,
R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,
R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,
R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅
⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅
= 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) :
R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,
R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,
R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,
R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅
⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅
= 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) :
R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) : R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) :
R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q0 q1 q2
qa
ε
0
1 0
1 0
1
ε
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs , q1) : R1 = ε,R2 = 0,R3 = 1,R4 = ∅ ⇒ ε0⋆1 | ∅ = 0⋆1
▶ (qs , qa) : R1 = ε,R2 = 0,R3 = ε,R4 = ∅ ⇒ ε0⋆ε | ∅ = 0⋆
▶ (q1, q1) : R1 = 1,R2 = 0,R3 = 1,R4 = ∅ ⇒ 10⋆1 | ∅ = 10⋆1
▶ (q1, qa) : R1 = 1,R2 = 0,R3 = ε,R4 = ∅ ⇒ 10⋆ε | ∅ = 10⋆
23/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶
(q1, q1) : R1 = 0,R2 = 1,R3 = 0,R4 = 10
⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) :
R1 = 0,R2 = 1,R3 = 0,R4 = 10
⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) : R1 = 0,
R2 = 1,R3 = 0,R4 = 10
⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) : R1 = 0,R2 = 1,
R3 = 0,R4 = 10
⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) : R1 = 0,R2 = 1,R3 = 0,
R4 = 10
⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) : R1 = 0,R2 = 1,R3 = 0,R4 = 10⋆1
⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1 q2
qa
0⋆1
0⋆
10⋆1
10⋆
0
0
1
We can eliminate the states in any order. Eliminate q2.
All pairs of states with transitions which are not ∅ through q2:
▶ (q1, q1) : R1 = 0,R2 = 1,R3 = 0,R4 = 10⋆1 ⇒ 01⋆0 | 10⋆1
Much easier!
24/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶
(qs , qa) : R1 = 0
⋆1,R2 = 01
⋆0 | 10⋆1,R3 = 10⋆,R4 = 0⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) :
R1 = 0
⋆1,R2 = 01
⋆0 | 10⋆1,R3 = 10⋆,R4 = 0⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) : R1 = 0⋆1,
R2 = 01
⋆0 | 10⋆1,R3 = 10⋆,R4 = 0⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) : R1 = 0⋆1,R2 = 01⋆0 | 10⋆1,
R3 = 10
⋆,R4 = 0
⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) : R1 = 0⋆1,R2 = 01⋆0 | 10⋆1,R3 = 10⋆,
R4 = 0
⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) : R1 = 0⋆1,R2 = 01⋆0 | 10⋆1,R3 = 10⋆,R4 = 0⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
q1
qa
0⋆1
0⋆
01⋆0 | 10⋆1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1:
▶ (qs , qa) : R1 = 0⋆1,R2 = 01⋆0 | 10⋆1,R3 = 10⋆,R4 = 0⋆
so (R1)(R2)⋆(R3) | (R4) = 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
25/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs qa
0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
So, 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆ is a RegEx which recognises binary
strings which are divisible by 3.
Eliminating states in a different order can result in a different, but
equivalent RegEx.
e.g. eliminating q2, q1, then q0 yields: (1(01⋆0)⋆1|0)⋆
26/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs qa
0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
So, 0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆ is a RegEx which recognises binary
strings which are divisible by 3.
Eliminating states in a different order can result in a different, but
equivalent RegEx.
e.g. eliminating q2, q1, then q0 yields: (1(01⋆0)⋆1|0)⋆
26/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
q0
q1
q2
a
b
As GNFA:
qs q0
q1
q2
qa
ε
a
b
ε
ε
27/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
q0
q1
q2
a
b
As GNFA:
qs q0
q1
q2
qa
ε
a
b
ε
ε
27/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0
q1
q2
qa
ε
a
b
ε
ε
Eliminate q2:
qs q0
q1
qa
ε
a
b∅⋆ε | ∅ = b
ε
28/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0
q1
q2
qa
ε
a
b
ε
ε
Eliminate q2:
qs q0
q1
qa
ε
a
b∅⋆ε | ∅ = b
ε
28/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0
q1
qa
ε
a
b
ε
Eliminate q1:
qs q0 qa
ε a∅⋆ε | b = a | b
29/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0
q1
qa
ε
a
b
ε
Eliminate q1:
qs q0 qa
ε a∅⋆ε | b = a | b
29/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0 qa
ε a | b
Eliminate q0:
qs qa
ε∅⋆(a | b) | ∅
Simplify, to get the expected:
qs qa
a | b
30/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0 qa
ε a | b
Eliminate q0:
qs qa
ε∅⋆(a | b) | ∅
Simplify, to get the expected:
qs qa
a | b
30/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs q0 qa
ε a | b
Eliminate q0:
qs qa
ε∅⋆(a | b) | ∅
Simplify, to get the expected:
qs qa
a | b
30/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Summary
Algorithm to convert an NFA to a RegEx:
1. Convert the NFA to a Generalised NFA (GNFA)
▶ Only one start state, no incoming transitions
▶ Only one accept state, no outgoing transitions
▶ Transitions described by RegEx
2. Progressively eliminate all states between start and accept
▶ For each pair (qi , qj ) where qi , qj ∈ Q \ {qelim}
▶ Replace arrow qi → qj with ((R1)(R2)⋆(R3) | (R4)), where
▶ R1 is the RegEx on transition qi → qelim
▶ R2 is the RegEx on transition qelim → qelim
▶ R3 is the RegEx on transition qelim → qj
▶ R4 is the RegEx on transition qi → qj
3. The transition between the start and the accept state is now a
regular expression describing L
31/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Summary
Algorithm to convert an NFA to a RegEx:
1. Convert the NFA to a Generalised NFA (GNFA)
▶ Only one start state, no incoming transitions
▶ Only one accept state, no outgoing transitions
▶ Transitions described by RegEx
2. Progressively eliminate all states between start and accept
▶ For each pair (qi , qj ) where qi , qj ∈ Q \ {qelim}
▶ Replace arrow qi → qj with ((R1)(R2)⋆(R3) | (R4)), where
▶ R1 is the RegEx on transition qi → qelim
▶ R2 is the RegEx on transition qelim → qelim
▶ R3 is the RegEx on transition qelim → qj
▶ R4 is the RegEx on transition qi → qj
3. The transition between the start and the accept state is now a
regular expression describing L
31/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Summary
Algorithm to convert an NFA to a RegEx:
1. Convert the NFA to a Generalised NFA (GNFA)
▶ Only one start state, no incoming transitions
▶ Only one accept state, no outgoing transitions
▶ Transitions described by RegEx
2. Progressively eliminate all states between start and accept
▶ For each pair (qi , qj ) where qi , qj ∈ Q \ {qelim}
▶ Replace arrow qi → qj with ((R1)(R2)⋆(R3) | (R4)), where
▶ R1 is the RegEx on transition qi → qelim
▶ R2 is the RegEx on transition qelim → qelim
▶ R3 is the RegEx on transition qelim → qj
▶ R4 is the RegEx on transition qi → qj
3. The transition between the start and the accept state is now a
regular expression describing L
31/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Outline
▶ Regular Expressions
▶ Equivalence of FA and Regular Expressions
▶ Proving if a language is, or is not, regular
32/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Proving if a language is regular or not
Recall the definition:
A language is regular if and only if there exists a finite automaton
which recognises it.
Suppose a language is regular. How can we prove it?
▶ Devise an NFA which recognises it, or
▶ Devise a DFA which recognises it, or
▶ Devise a RegEx which describes it
What if the language was not regular? How can we prove that no
suitable automata exists? We can use the pumping lemma for
regular langauges
33/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Proving if a language is regular or not
Recall the definition:
A language is regular if and only if there exists a finite automaton
which recognises it.
Suppose a language is regular. How can we prove it?
▶ Devise an NFA which recognises it, or
▶ Devise a DFA which recognises it, or
▶ Devise a RegEx which describes it
What if the language was not regular? How can we prove that no
suitable automata exists? We can use the pumping lemma for
regular langauges
33/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Proving if a language is regular or not
Recall the definition:
A language is regular if and only if there exists a finite automaton
which recognises it.
Suppose a language is regular. How can we prove it?
▶ Devise an NFA which recognises it, or
▶ Devise a DFA which recognises it, or
▶ Devise a RegEx which describes it
What if the language was not regular? How can we prove that no
suitable automata exists? We can use the pumping lemma for
regular langauges
33/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Pumping s using y
q0 qi f
Q
Q
Q
x
y
z
Suppose some string s exists, passing through M :
▶ From q0 to qi , using a string x , then
▶ from qi back to qi , using a string y ̸= ε, then
▶ from qi to some accept state f ∈ F , using a string z
Then s = xyz ∈ L, and xyk z ∈ L for all k ≥ 0
e.g. if x = aa, y = b, z = c, then {aac, aabc, aabbc, …} ⊆ L
34/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Pumping s using y
q0 qi f
Q
Q
Q
x
y
z
Suppose some string s exists, passing through M :
▶ From q0 to qi , using a string x , then
▶ from qi back to qi , using a string y ̸= ε, then
▶ from qi to some accept state f ∈ F , using a string z
Then s = xyz ∈ L, and xyk z ∈ L for all k ≥ 0
e.g. if x = aa, y = b, z = c, then {aac, aabc, aabbc, …} ⊆ L
34/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Long strings in finite automata
q0 qi f
Q
Q
Q
x
y
z
Suppose M is a DFA with n states, and s ∈ L(M ), but |s| > n +1
Then there exists at least one state which was visited more than
once (qi), and a substring y ̸= ε corresponding to the path
followed between the two of those visits.
Hence we can pump s to find other strings in the language
35/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Long strings in finite automata
q0 qi f
Q
Q
Q
x
y
z
Suppose M is a DFA with n states, and s ∈ L(M ), but |s| > n +1
Then there exists at least one state which was visited more than
once (qi), and a substring y ̸= ε corresponding to the path
followed between the two of those visits.
Hence we can pump s to find other strings in the language
35/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Long strings in finite automata
q0 qi f
Q
Q
Q
x
y
z
Suppose M is a DFA with n states, and s ∈ L(M ), but |s| > n +1
Then there exists at least one state which was visited more than
once (qi), and a substring y ̸= ε corresponding to the path
followed between the two of those visits.
Hence we can pump s to find other strings in the language
35/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Finite automata, infinite languages
All finite languages are regular. (Why?)
Suppose L is an infinite regular language.
▶ L is regular, so a DFA M exists which recognises it.
▶ L is an infinite set over a finite alphabet, so it must include
arbitrarily long words.
▶ Therefore words exist which can be pumped
36/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Finite automata, infinite languages
All finite languages are regular. (Why?)
Suppose L is an infinite regular language.
▶ L is regular, so a DFA M exists which recognises it.
▶ L is an infinite set over a finite alphabet, so it must include
arbitrarily long words.
▶ Therefore words exist which can be pumped
36/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Pumping lemma for regular languages
If L is a regular language, then there exists a number p (the
pumping length) such that for any string s ∈ L of length at least
p, then s may be divided into three pieces, s = xyz , such that:
1. xyk z ∈ L for all k ≥ 0 (i.e. we can use y to pump the string)
2. |y | > 0 (i.e. y ̸= ε)
3. |xy | ≤ p
If a language does not satisfy this lemma, then it cannot be regular
37/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Using the pumping lemma
We can (only) use the pumping lemma to prove that a language is
not regular
Proof by contradiction:
1. Assume that the langage is regular
2. Choose an appropriate string in the language
▶ This is often the hardest part of the proof
▶ We must find one which will allow us to:
3. Apply the lemma to find a contradiction
4. Thereby deduce that the assumption is false
▶ i.e. The language cannot be regular
38/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn |n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma.
3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that
4.1 xyk z ∈ L for all k ≥ 0 (i.e. we can pump y)
4.2 |y | > 0
4.3 |xy | ≤ p
5. Therefore y = a i for some 0 < i ≤ p (at least one a, no b’s)
6. Let k = 2. Then xyk z has more a’s than b’s, so xyk z ̸∈ L
7. Lines 6 and 4.1 form a contradiction, therefore the
assumption is false (i.e. L is not regular.)
39/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introduction
So far we have seen two different, but equivalent, methods of
describing languages: finite automata and regular expressions,
which describe regular languages
We have already proven that some languages, such as
{0n1n | n ≥ 0}, cannot be described using FA or RE.
Today we will introduce context-free grammars (CFG), which
describe the next category of languages, the context-free languages
Later, will see grammars called regular grammars, which describe
exactly regular languages
40/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Grammars
Grammars are another way to describe a language
A grammar is a set of rules which can be used to generate a
language
The language generated is the set of all strings which can be
derived from the grammar
41/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
42/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S
⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
42/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
42/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
42/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G1)
S → 01 Base case: 01 ∈ L
S → 0S1 Recursive case: if S ∈ L then 0S1 ∈ L
G1 generates the language L = {0n1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S ⇒ 0S1 using rule S → 0S1
⇒ 00S11 using rule S → 0S1
⇒ 000111 using rule S → 01
42/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G2)
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
What language does G2 generate?
{ the girl likes the girl, the girl likes the ball,
the girl sees the girl, the girl sees the ball,
the ball likes the girl, the ball likes the ball,
the ball sees the girl, the ball sees the ball }
43/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Introductory example (G2)
S → NounPhrase VerbPhrase
NounPhrase → the Noun
VerbPhrase → Verb NounPhrase
Noun → girl | ball
Verb → likes | sees
What language does G2 generate?
{ the girl likes the girl, the girl likes the ball,
the girl sees the girl, the girl sees the ball,
the ball likes the girl, the ball likes the ball,
the ball sees the girl, the ball sees the ball }
43/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Definitions
Terminals
▶ The finite set of symbols which make up strings of the
language
Non-terminals / Variables
▶ A finite set of symbols used to generate the strings.
▶ They never appear in the language.
Start symbol
▶ The variable used to start every derivation
44/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
45/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
45/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Definitions
Production rules
▶ Sometimes called substitution or derivation rules
▶ Define strings of variables and terminals which can be
substituted for a variable:
Variable →
A variable can have many rules:
Noun → girl
Noun → ball
Noun → quokka
They can be written together:
Noun → girl | ball | quokka
45/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Another example
S → T | (S · S ) | (λT .S )
T → a | b | …
This is a grammar for lambda calculus expressions
▶ The variables are S ,T
▶ S is the start variable
▶ The terminals are a, b, …, (, ), λ, ., · (i.e. atoms and operators)
46/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Some common notational conventions
If not stated otherwise:
▶ A,B ,C , … and S are variables
▶ S is the start variable
▶ a, b, c, … are terminals
▶ …,X ,Y ,Z are either terminals or variables
▶ …w , x , y , z are strings of terminals only
▶ α, β, γ, … are strings of terminals and/or variables
47/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
NIL
In your tree encoding, NIL should represent the empty tree (a tree
with no nodes)
This is the same idea as NIL for a Church List
If you need to use both and they are different, then you could
rename them. e.g.
▶ NIL = PAIR TRUE TRUE , for Church Lists
▶ NILTREE , for your tree encoding
48/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example answer
(HEAD z ) should be the head of list z
HEAD = λz .FIRST (SECOND z )
The second pair in a Church list contains the data [head , tail ], so
we just need to get the first expression from the second pair.
Example: head of {1, 2, 3} should be 1
HEAD {1, 2, 3}
= HEAD (CONS 1 {2, 3}) (list notation)
= HEAD (PAIR TRUE (PAIR (1 {2, 3}))) (defn. of CONS)
= (λz .FIRST (SECOND z ))(PAIR TRUE (PAIR 1 {2, 3})))
(defn. of HEAD)
= FIRST (SECOND (PAIR TRUE (PAIR 1 {2, 3}))))
= FIRST (PAIR 1 {2, 3})) (reduced SECOND)
= 1 (reduced FIRST)
49/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Immutable data structures
Data structures encoded in lambda calculus are immutable.
▶ We can’t change them
▶ Instead, we return a new expression
50/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: Delete the second element of a list
DELETE_SECOND = λz .CONS (HEAD z ) (TAIL (TAIL z ))
▶ CONS to make a new list using:
▶ the head of the old list
▶ the tail of the tail of the old list
▶ i.e. we skipped the second element
51/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: Insert e to the second position of a
list
INSERT_SECOND = λez .CONS (HEAD z ) (CONS e (TAIL z ))
▶ CONS a new list using:
▶ the head of the old list
▶ e
▶ the tail of the old list
52/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Recursive data structures
Linked Lists
▶ Each position has a reference (link) to the next one
Church Lists are similar, except instead of linking to the next node,
they link to the list which starts with the next node
▶ CONS head tail
▶ head is the element stored at the start of the list
▶ tail is the sublist containing all the remaining elements
53/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Recursive data structures
You can implement a tree data structure in a very similar way.
Except instead of linking to a single tail, they have a left sub-tree
and a right sub-tree.
In your assignment, MAKETREE needs to be an expression
which will take a number to store, and two trees (which will be the
left and right children).
54/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Java example
pub l i c c l a s s Tree {
pub l i c f i n a l i n t e l ement ;
pub l i c f i n a l Tree l e f t ;
pub l i c f i n a l Tree r i g h t ;
pub l i c Tree ( i n t e lement , Tree l e f t , Tree r i g h t ) {
t h i s . e l ement = e lement ;
t h i s . l e f t = l e f t ;
t h i s . r i g h t = r i g h t ;
}
}
MAKETREE in the assignment is like writing: new Tree(e,a,b);
55/62
Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Recursive functions
Simple recursion, condition decides if you’re at the base case
H = λfxyz .(condition)(base)(recursive)
F = (Y H )
You can have more complicated logic if you want:
H = λfxy .(< x 5) ( (< y 5) y (f 1 x ) ) ( (= x y) (f y x ) 3 ) F = (Y H ) ▶ If x < 5 and y < 5 then y (base case) ▶ If x < 5 and y ≥ 5 then f (1, x ) (recursive case) ▶ If x ≥ 5 and x = y then f (y , x ) (recursive case) ▶ If x ≥ 5 and x ̸= y then 3 (base case) 56/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review Helper functions It’s a good idea to define some extra expressions sometimes ▶ To make long/complex expressions easier to read ▶ To reduce repetition if you need the expression in several places Example: a MAX function which returns the larger of two numbers would be helpful when calculating the height of a tree 57/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review LISP I discourage you from trying to directly implement your lambda calculus expressions in LISP. It’ll mostly work, but some things get messy (especially conditional logic) if you try to implement everything as (lambda) expressions. I recommend using Lisp lists to store data. e.g. ▶ A Church pair can be represented by a Lisp list with only two elements ▶ A Church list can be represented by a Lisp list Then you can just use standard Lisp list operations to manipulate your data, instead of needing to implement all your lambda calculus expressions directly. 58/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review LISP Don’t forget to indent your code to make it easier to see what is being applied to what. Most errors people have shown me were just scope errors. ; ; example o f do ing an i f s ta t ement ( defun f oo ( x y ) ( i f ( . . . ) ; ; some c o n d i t i o n ( . . . ) ; ; t r u e ca s e ( . . . ) ; ; f a l s e ca s e ) ) 59/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review LISP ; ; example o f a ne s t ed i f s t a t ement ( defun f oo ( x y ) ( i f ( . . . ) ; ; c o n d i t i o n 1 ( i f ; ; t r u e 1 ( . . . ) ; ; c o n d i t i o n 2 ( . . . ) ; ; t r u e 2 ( . . . ) ; ; f a l s e 2 ) ( . . . ) ; ; f a l s e 1 ) ) 60/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review LISP You don’t need any notation we haven’t provided in tutorials or lectures. Look back at the earlier tutorials and solutions for some code examples. 61/62 Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review Regular Expressions ▶ What they are and how to use them ▶ Regular operations Equivalence of FA and Regular Expressions ▶ Convert an NFA to a RegEx ▶ Convert a RegEx to an NFA Proving if a language is, or is not, regular ▶ Prove regularity by finding a DFA, NFA, or RegEx ▶ Prove non-regularity by finding a contradiction in the Pumping Lemma Grammars (basic concepts) Lambda calculus revision 62/62 Outline outline RegEx NFA outline Construction example NFA RegEx simple examples notion GNFA conversion of NFA to GNFA simple example state elimination fully worked example another simple example summary of NFA to RegEx algorithm Proving Regularity outline Pumping lemma: idea Pumping lemma: definition Pumping lemma: use Grammars introduction definition example definitions Lambda Calculus Lambda Calculus Immutable Data Review review