程序代写代做代考 Java Lambda Calculus algorithm data structure COMP2022: Formal Languages and Logic - 2018, Semester 2, Week 6

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

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 ∈ Σ

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:

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

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

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

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⋆

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

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:

1 0

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

∅ ∅

∅

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

∅ ∅

∅

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.

a, b

qs q1

q2qa

ε
a

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

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

R1 R3

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

1 0

Convert to GNFA:

0 1 0

1 0

22/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 2: divisible by 3

q0 q1 q2

1 0

Convert to GNFA:

0 1 0

1 0

22/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 2: divisible by 3

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

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

q0 q1 q2

1 0

We can eliminate the states in any order. Eliminate q0.

23/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 2: divisible by 3

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

q1 q2

0⋆1
0⋆

10⋆1

10⋆

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

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

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

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

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

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

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

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

As GNFA:

qs q0

qa
ε

27/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 3: Multiple accept states

As GNFA:

qs q0

qa
ε

27/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 3: Multiple accept states

qs q0

qa
ε

Eliminate q2:

qs q0

qa
ε

b∅⋆ε | ∅ = b

28/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 3: Multiple accept states

qs q0

qa
ε

Eliminate q2:

qs q0

qa
ε

b∅⋆ε | ∅ = b

28/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review

Example 3: Multiple accept states

qs q0

qa
ε

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
ε

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

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

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

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

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

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

⇒ 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

Related Posts