COMP2022: Formal Languages and Logic – 2018, Semester 2, Week 4
COMP2022: Formal Languages and Logic
2018, Semester 2, Week 4
Joseph Godbehere
23rd August, 2018
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or
on behalf of the University of Sydney pursuant to part VB of the
Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright
under the Act. Any further copying or communication of this
material by you may be subject of copyright protect under the Act.
Do not remove this notice.
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
outline
▶ Lambda Calculus
▶ Concepts (Operators, FV, Reductions)
▶ Recursion (fixed point, using it)
▶ β-equivalence
▶ Computational power
▶ Functional Programming
▶ Automata Theory
▶ Background, concepts
▶ DFA
▶ Regular languages
▶ NFA
3/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Operators
▶ Application
▶ Notation: (A · B)
▶ Expression B is applied to expression A
▶ Left associative: ABCDEF = (((((AB)C )D)E )F )
▶ Abstraction
▶ (λx .M )
▶ Variable x is abstracted in expression M
▶ Right associative:
(λabcdef .M ) = (λa.(λb.(λc.(λd .(λe.(λf .M ))))))
4/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Operators
▶ Application
▶ Notation: (A · B)
▶ Expression B is applied to expression A
▶ Left associative: ABCDEF = (((((AB)C )D)E )F )
▶ Abstraction
▶ (λx .M )
▶ Variable x is abstracted in expression M
▶ Right associative:
(λabcdef .M ) = (λa.(λb.(λc.(λd .(λe.(λf .M ))))))
4/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Free Variables
Formally, the set of free variables of an expression is defined
inductively like this:
FV (x ) = x (where x is an atom)
FV (MN ) = FV (M ) ∪ FV (N ) (M ,N are expressions)
FV (λx .M ) = FV (M )−{x}
Any variable in an expression that is not free, is bound.
5/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Rewriting
▶ M [x := N ]
▶ Expression M , but all free occurrences of x are replaced with
N
▶ e.g.
▶ (xyzλx .(zxz ))[x := A] ≡ (Ayzλx .(zxz ))
▶ (xyzλx .(zxz ))[y := B ] ≡ (xBzλx .(zxz ))
▶ (xyzλx .(zxz ))[z := C ] ≡ (xyCλx .(CxC ))
6/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
α-reduction
▶ λx .M = λy .(M [x := y ])
▶ Renames a λ to remove a name conflict
▶ y must be a new variable
▶ Do not choose a symbol that is already in the expression
▶ It’s usually easiest to start with the innermost λ
7/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
β-reduction
▶ (λx .M ) ·N = M [x := N ]
▶ Reduces an application into an abstraction
▶ Note: the free occurrences of x in M are exactly the set of
occurrences which are bound to the λx . in (λx .M )
▶ Do α-reductions first if necessary
8/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
η-reduction
▶ If x is not free in M (i.e. x ̸∈ FV (M )), then we can write:
λx .Mx = M
▶ Reduces an abstraction directly
9/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Naming
Naming conflicts:
▶ If a variable is free, but there is also λ with the same label
▶ If more than one λ uses the same label
▶ They can cause problems with β reduction!
To fix them:
▶ Apply α-reduction repeatedly to change the λ labels
▶ Always rename to a label not already in use
▶ Work from the innermost λ to the outermost one
10/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Fixed Point Combinators
A fixed point combinator is a combinator which has a fixed point.
We say F has a fixed point if ∃X (FX = X )
i.e. some input X exists which, when applied to F , outputs X
again.
11/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Fixed Point Theorem
1. ∀F ∃X FX = X
▶ All functions have a fixed point
▶ Proven last week
2. There is a fixed point combinator Y such that
∀F F (YF ) = YF
▶ Y = λf .
(
λx .f (xx )
)(
λx .f (xx )
)
▶ i.e. for any function F , YF is a fixed point of F .
▶ Proven last week
▶ Very useful for recursion
12/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Recursion
Recursive functions often look like this:
F =
(
λxyz .(condition)(base case)(recursive case calls F )
)
If we need more cases, we can just add more logic
We can’t directly refer to the function F within itself
We can define it like this instead:
H =
(
λfxyz .(condition)(base case)(recursive case calls f )
)
F = Y H
13/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
H =
(
λfxyz .(condition)(base case)(recursive case calls f )
)
F = Y H
Evaluation:
F a b c = (Y H ) a b c
= H (Y H ) a b c (YH is a fixed point of H )
=
(
λfxyz .(condition)(base)(call(s) to f )
)
(Y H ) a b c
=
(
λxyz .(condition)(base)(call(s) to (Y H ))
)
a b c
Notice that we managed to call (Y H ) = F from within F
▶ recursion!
14/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Reducing the Y Combinator
We don’t need to reduce (Y H ) directly
▶ In the recursive calls, it expands to H (Y H ), then we reduce
the leftmost H
▶ The (Y H ) will disappear when we reach the base cases
15/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example: last week’s tutorial questions
We wanted a function that would build a list {x1…xn} from an
expression like (Fnx1…xn)
Key ideas:
▶ Recurse n times
▶ Each recursion consumes up one argument
▶ Base case n = 0
H = λftn.(ISZERO n) t
(
λe.f (CONS e t) (PRED n)
)
F = YHNIL
▶ Prepend the next argument to the list with (CONSet), and
recursively call f list (n − 1) with the remaining arguments
16/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example: last week’s tutorial questions
F 3 a b c
= Y H NIL 3 a b c
= H (Y H ) NIL 3 a b c
=
(
λftn.(ISZERO n) t
(
λe.f (CONS e t) (PRED n)
))
(Y H ) NIL 3 a b c
= … = (ISZERO 3) NIL
(
λe.(Y H ) (CONS e NIL) (PRED 3)
)
a b c
= … = FALSE NIL
(
λe.(Y H ) (CONS e NIL) (PRED 3)
)
a b c
= … =
(
λe.(Y H ) (CONS e NIL) (PRED 3)
)
a b c
= … = (Y H ) (CONS a NIL) (PRED 3) b c
= … = (Y H ) (CONS a NIL) 2 b c
= … = (Y H ) (CONS b (CONS a NIL)) 1 c
= … = (Y H ) (CONS c (CONS b (CONS a NIL)) 0
= … = (CONS c (CONS b (CONS a NIL))) 17/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example: last week’s tutorial questions
Reversing a list:
H = λfab.(ISNIL a) b (f (TAIL a)(CONS (HEAD a) b))
F = λa.Y H a NIL
F {c, b, a}
=(λa.Y H a NIL){c, b, a}
=Y H {c, b, a} NIL
=H (Y H ) {c, b, a} NIL
=
(
λfab.(ISNIL a) b (f (TAIL a)(CONS (HEAD a) b))
)
(Y H ) {c, b, a} NIL
=… = (Y H ) (TAIL {c, b, a})(CONS (HEAD {c, b, a}) NIL)
=… = (Y H ) {b, a}(CONS c NIL)
=… = (Y H ) {b, a}{c}
=… = (Y H ) {a}{b, c}
=… = (Y H ) NIL{a, b, c}
=… = {a, b, c} 18/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Notation
We’ve mostly been using the = sign everywhere. This isn’t strictly
correct!
We could have used more precise notation, such as:
▶ M = N : M is the same as N
▶ M ≡ N : M is equivalent to N (has the same effect)
▶ M ↠β N : M β-reduces to N
▶ M →β N : M β-reduces to N (in one step)
▶ M =β N : M is β-convertable to N
We’ve avoided using these so far for the sake of simplicity
19/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
β-normal form
An expression is in β-normal form if no β-reductions are available
Not all expressions have normal forms
▶ e.g. (λx .xx )(λx .xx ) does not have a normal form
Normalisation Theorem: If a normal form exists, it can always be
found by following the leftmost reduction
▶
(
(λx .xx )(λx .xx )
)
(λab.b) does not have a normal form,
because the leftmost reduction loops infinitely
▶ (λab.b)
(
(λx .xx )(λx .xx )
)
has a normal form, (λb.b), even
though following the reduction on the right would not have
found it
20/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
β-equivalence
Two expressions are β-equivalent if they have a common reduct
▶ This doesn’t necessarily mean we can β-reduce between them
directly!
▶ e.g.
▶ (λxy .x )ab and (λxy .x )ac both reduce to a
▶ Therefore, they are β-equivalent
▶ … even though we have no way to reduce between them!
▶ We’ve been using this property often, without stating it
21/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
β-equivalence
An interesting example of β-equivalence is the Y Combinator:
YF =β F (YF ), but neither YF ↠β F (YF ) nor F (YF ) ↠β YF
Turing discovered another fixed point combinator
Θ ≡
(
λxy .y(xxy)
)(
λxy .y(xxy)
)
, which has the property that
ΘF ↠β F (ΘF )
There are an infinite number of fixed point combinators in untyped
lambda calculus!
22/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Church-Rosser theorem
If M ↠β N1 and M ↠β N2, then there exists some N3 such that
N1 ↠β N3 and N2 ↠β N3
This is the property we’ve been using to claim that the order in
which we reduce the subexpressions doesn’t change the result.
We do need to be a little bit careful sometimes, as some paths do
not lead to the normal form, although they remain β-equivalent to
it!)
23/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Computational Power
Lambda calculus can compute all the computable (recursive)
functions.
▶ Proof is beyond the scope of this course
▶ Key points:
▶ We have numbers and arithmetic operations
▶ All recursive functions are λ-definable
▶ Lambda Calculus is consistent (you can’t prove false
statements)
▶ If a normal form exists, we can find it (Normalisation Theorem)
▶ If a normal form exists, it is unique
Essentially, given any problem you can express with set theory (i.e.
maths), then if it’s possible to solve (compute) it, lambda calculus
can do so.
24/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Computational Power
Later in the course we will look at Turing machines.
The Church-Turing hypothesis shows that lambda calculus and
Turing machines have the same computational power.
The proof is relatively simple. If we have time at the end of the
course, we will show you.
25/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Why?
If we can do just as much using the imperative paradigm, then why
use the functional paradigm?
≡ is not =
▶ They have equivalent computational power
▶ They are not the same
▶ Some things are easier with each approach
26/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Positive traits of functional paradigm
▶ Often easier to write concurrent code (Church-Rosser)
▶ Often easier to prove correctness
▶ Lazy evaluation
▶ Easy to work with vast / infinite data sets
▶ Function composition makes some tasks much simpler
▶ e.g. Map / fold / reduce templates allow us to define ways to
‘crawl’ over our data. Performing different transformations
now just becomes arguments to these methods, instead of
entirely new functions.
▶ Inherent immutability
▶ Our functions define relationships between the existing
structure and the one we want
▶ Notions like undo/redo become almost trivial
27/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Hybrid languages
NOT an either/or choice.
Most languages blend imperative and functional paradigms:
▶ e.g. Java, C++, Python, ….
▶ … because it’s so useful to be able to do both
28/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
outline
▶ Lambda Calculus
▶ Concepts (Operators, FV, Reductions)
▶ Recursion (fixed point, using it)
▶ β-equivalence
▶ Computational power
▶ Functional Programming
▶ Automata Theory
▶ Background, concepts
▶ DFA
▶ Regular languages
▶ NFA
29/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Alan Turing
▶ Founder of computer science, mathematician,
philosopher, code breaker, visionary
▶ Created abstract machines called Turing
machines in the 1930s, before computers
existed
▶ Church-Turing thesis
▶ Turing test
▶ Can machines think?
▶ The Imitation Game
▶ Enigma code breaker
30/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Noam Chomsky
▶ Linguist, philosopher, cognitive scientist,
logician, historian, political critic and activist
▶ Chomsky Hierarchy: a containment hierarchy
of classes of formal languages (applies to
human language and computer theory)
Regular
(DFA)
Context-
free
(PDA)
Context-
sensitive
(LBA)
Recursively-
enumerable
(TM)
31/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Alphabet
An alphabet is a finite, non-empty set of symbols, denoted Σ
For example:
▶ Binary: Σ = {0, 1}
▶ All lower case letters: Σ = {a, b, c, …, z}
▶ Alphanumerics: Σ = {a, …, z ,A, …,Z , 0, …, 9}
▶ ASCII, unicode
▶ Set of signals used by a protocol
32/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String
▶ A string is a finite sequence of symbols from Σ. For example
“01110”, “alice”, “Bnode.java”
▶ The length of a string w , denoted |w |, is equal to the number
of symbols in the string. e.g. if x = abcd then |x | = 4
▶ Σ∗ denotes the set of all strings over the alphabet Σ
▶ ε (epsilon) denotes the empty string
▶ |ε| = 0
▶ if x = abεcεdε then |x | = ?
4
▶ xy = the concatenation of two strings x and y
▶ xn the string x repeated n times
33/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String
▶ A string is a finite sequence of symbols from Σ. For example
“01110”, “alice”, “Bnode.java”
▶ The length of a string w , denoted |w |, is equal to the number
of symbols in the string. e.g. if x = abcd then |x | = 4
▶ Σ∗ denotes the set of all strings over the alphabet Σ
▶ ε (epsilon) denotes the empty string
▶ |ε| = 0
▶ if x = abεcεdε then |x | = ? 4
▶ xy = the concatenation of two strings x and y
▶ xn the string x repeated n times
33/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Powers of an alphabet
Let Σ be an alphabet, then:
▶ Σk is the set of all strings of length k
▶ Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ … (i.e. all strings, including ε)
▶ Σ+ = Σ1 ∪ Σ2 ∪ Σ3 ∪ … (i.e. all strings except ε)
34/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Languages
▶ A language L over alphabet Σ is a subset of Σ∗ (i.e. L ⊆ Σ∗)
▶ Examples:
▶ Let L be the language of all strings consisting of n 0s followed
by n 1s:
▶ L = {ε, 01, 0011, 000111, …}
▶ L = {0n1n |n ≥ 0}
▶ Let L be the language of all strings with an equal number of
0s and 1s:
▶ L = {ε, 01, 10, 0011, 0101, 0110, 1001, 1010, 1100, …}
▶ ∅ denotes the empty language
▶ Beware: {ε} is NOT ∅
35/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
The Membership problem
Problem:
Given a string w ∈ Σ∗ and a language L over Σ, decide whether or
not w ∈ L
Example:
Let w = 100011
Does w belong to the language of strings with an equal number of
0s and 1s?
36/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
outline
▶ Lambda Calculus
▶ Concepts (Operators, FV, Reductions)
▶ Recursion (fixed point, using it)
▶ β-equivalence
▶ Computational power
▶ Functional Programming
▶ Automata Theory
▶ Background, concepts
▶ DFA
▶ Regular languages
▶ NFA
37/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Formal model which remembers only a finite amount of
information
▶ Information is represented by the state (circles)
▶ Transition rules (arrows) define state changes according to
input
▶ Start state is denoted →
▶ Accept state(s) denoted by double circle
▶ The set of all possible input symbols is the alphabet, Σ
38/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Given a sequence of input symbols:
▶ Begin in the start state
▶ Follow one transition for each symbol in the input string
▶ After reading the entire input string:
▶ The input is accepted if the automaton is in an accept state
▶ The input is rejected if it is not
39/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf Yes
▶ pdf No
▶ example.pd No
▶ example.pdf.pdf No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf
Yes
No
▶ example.pd
No
▶ example.pdf.pdf
No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf Yes
▶ pdf
No
▶ example.pd
No
▶ example.pdf.pdf
No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf Yes
▶ pdf No
▶ example.pd
No
▶ example.pdf.pdf
No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf Yes
▶ pdf No
▶ example.pd No
▶ example.pdf.pdf
No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Example input “example.pdf”:
▶ loops on q0 through “example”
▶ moves to q1 when it scans ‘.’
▶ then q2 for ‘p’, q3 for ‘d’, q4 for ‘f’
▶ after all input is scanned, we ended in an accept state,
therefore “example.pdf” is accepted
How about:
▶ .pdf Yes
▶ pdf No
▶ example.pd No
▶ example.pdf.pdf No(!)
40/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Recall:
▶ Information is represented by the state (circles)
What information is represented by state q1? By q2?
▶ q1: We have scanned any number of letters, followed by ‘.’
▶ q2: We have scanned any number of letters, followed by “.p”
41/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Recall:
▶ Information is represented by the state (circles)
What information is represented by state q1? By q2?
▶ q1: We have scanned any number of letters, followed by ‘.’
▶ q2: We have scanned any number of letters, followed by “.p”
41/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
q0 q1 q2 q3 q4
Σ \ {.}
. p d f
Recall:
▶ Information is represented by the state (circles)
What information is represented by state q1? By q2?
▶ q1: We have scanned any number of letters, followed by ‘.’
▶ q2: We have scanned any number of letters, followed by “.p”
41/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Our first valid DFA
A properly defined DFA will have a transition for every symbol,
from every state:
q0 q1 q2 q3 q4
Σ \ {.}
. p
.
Σ \ {., p}
d
.
Σ \ {., d}
f
.
Σ \ {., f }
.
Σ \ {.}
42/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Alternative notation
You can be more descriptive if you like:
ends:
other
ends:
.
ends:
.p
ends:
.pd
ends:
.pdf
not .
. p
.
not . or p
d
.
not . or d
f
.
not . or f
.
not .
43/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Deterministic Finite Automata (DFA)
Informal definition:
1. They have a finite set of states
2. They have a finite alphabet of symbols
3. They have one start state
4. They have a behaviour given by transitions
▶ Exactly one for each alphabet symbol, from each state
5. They have accept state(s)
44/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Deterministic Finite Automata (DFA)
Formal definition:
A finite automaton is a 5-tuple (Q ,Σ, δ, q0,F ) where
1. Q is a finite set called the states,
2. Σ is a finite set called the alphabet,
3. δ : Q × Σ → Q is the transition function,
4. q0 ∈ Q is the start state, and
5. F ⊆ Q is the set of accept states.
45/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Draw a DFA from the definition
Let M1 = (Q ,Σ, δ, q0,F ) where:
1. Q = {q0, q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by
0 1
q0 q0 q1
q1 q2 q1
q2 q1 q1
4. q0 ∈ Q is the start state
5. F = {q1}
Now we can draw M1:
q0 q1 q2
0
1
0
1
0,1
46/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Draw a DFA from the definition
Let M1 = (Q ,Σ, δ, q0,F ) where:
1. Q = {q0, q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by
0 1
q0 q0 q1
q1 q2 q1
q2 q1 q1
4. q0 ∈ Q is the start state
5. F = {q1}
Now we can draw M1:
q0 q1 q2
0
1
0
1
0,1
46/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q =
{q1, q2}
2. Σ =
{0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is:
q1
5. The set of accept states is: F =
{q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ =
{0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is:
q1
5. The set of accept states is: F =
{q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is:
q1
5. The set of accept states is: F =
{q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is:
q1
5. The set of accept states is: F =
{q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is: q1
5. The set of accept states is: F =
{q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is: q1
5. The set of accept states is: F = {q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
q1 q2
0
1
0
1
We can formally describe M2 as:
1. Q = {q1, q2}
2. Σ = {0, 1}
3. δ : Q × Σ → Q is given by:
0 1
q1 q1 q2
q2 q1 q2
4. The start state is: q1
5. The set of accept states is: F = {q2}
Some strings where M2 ends on an accept state are:
01, 0111, 0101
47/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
outline
▶ Lambda Calculus
▶ Concepts (Operators, FV, Reductions)
▶ Recursion (fixed point, using it)
▶ β-equivalence
▶ Computational power
▶ Functional Programming
▶ Automata Theory
▶ Background, concepts
▶ DFA
▶ Regular languages
▶ NFA
48/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Formal definition of computation
Let M = (Q ,Σ, δ, q0,F ) be a finite automaton, and
Let w = w1w2 · · ·wn be a string over the alphabet Σ
Then M accepts w if there exists a sequence of states r0r1 · · · rn
from Q which satisfy the following three conditions:
1. r0 = q0
2. δ(ri ,wi+1) = ri+1 for i = 0, . . . ,n − 1
3. rn ∈ F
49/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Language of an automaton
▶ Automata of all kinds define languages
▶ Let A be a language, and M be an automaton.
▶ We say that M recognises A if and only if
A = {w |M accepts w}
▶ We often denote the language recognised by M as L(M )
▶ L(M ) is the set of all strings labelling paths from the start
state of M to any accept state in M
50/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Regular Language
A language is regular if and only if there exists a finite automaton
which recognises it.
Exercise:
Prove that A = {w |w is the empty string or ends with a 0} is a
regular language
Solution:
The following DFA recognises A, therefore A must be regular:
q0 q1
0
1
0
1
51/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Regular Language
A language is regular if and only if there exists a finite automaton
which recognises it.
Exercise:
Prove that A = {w |w is the empty string or ends with a 0} is a
regular language
Solution:
The following DFA recognises A, therefore A must be regular:
q0 q1
0
1
0
1
51/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
What language is accepted by M1?
q0 q1 q2
0
1
0
1
0,1
L(M1) = {w |w contains at least one 1 and an
even number of 0s follow the last 1}
52/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
What language is accepted by M1?
q0 q1 q2
0
1
0
1
0,1
L(M1) = {w |w contains at least one 1 and an
even number of 0s follow the last 1}
52/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
q1 q2
0
1
0
1
What language is accepted by M2?
L(M2) = {w |w ends with a 1}
What is the language recognised by the automaton obtained by
inversing the accept and start states in M2?
53/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
q1 q2
0
1
0
1
What language is accepted by M2?
L(M2) = {w |w ends with a 1}
What is the language recognised by the automaton obtained by
inversing the accept and start states in M2?
53/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Designing finite automata
“Reader as Automaton” method: The states encode what you
need to remember about the string as you are reading it.
Example: Let Σ = {0, 1}. Devise an automaton which accepts the
language consisting of strings with an odd number of 1s.
We need to remember:
▶ There has been an even number of 1s so far
▶ There has been an odd number of 1s so far
So we will need exactly two states. Then it just remains to add the
transitions and define the start and accept states.
qeven qodd
0
1
1
0
54/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Designing finite automata
“Reader as Automaton” method: The states encode what you
need to remember about the string as you are reading it.
Example: Let Σ = {0, 1}. Devise an automaton which accepts the
language consisting of strings with an odd number of 1s.
We need to remember:
▶ There has been an even number of 1s so far
▶ There has been an odd number of 1s so far
So we will need exactly two states. Then it just remains to add the
transitions and define the start and accept states.
qeven qodd
0
1
1
0
54/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 2
Devise an automaton which accepts the language of strings which
begin and end with 1, over {0, 1}
We need to remember:
▶ Whether or not the string began with 1
▶ Whether or not the last character scanned was a 1
start scan 1 scan 0
error
0
1
0
1
1
0
0, 1
55/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 2
Devise an automaton which accepts the language of strings which
begin and end with 1, over {0, 1}
We need to remember:
▶ Whether or not the string began with 1
▶ Whether or not the last character scanned was a 1
start scan 1 scan 0
error
0
1
0
1
1
0
0, 1
55/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 3
Devise an automaton which accepts the language of binary strings
which do not contain 11
What do we need to remember?
▶ A: String so far has no 11, does not end in 1
▶ B: String so far has no 11, but ends with a single 1
▶ C: Consecutive 1s have been seen
A B C
0
1
0
1
0,1
56/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 3
Devise an automaton which accepts the language of binary strings
which do not contain 11
What do we need to remember?
▶ A: String so far has no 11, does not end in 1
▶ B: String so far has no 11, but ends with a single 1
▶ C: Consecutive 1s have been seen
A B C
0
1
0
1
0,1
56/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 3
Devise an automaton which accepts the language of binary strings
which do not contain 11
What do we need to remember?
▶ A: String so far has no 11, does not end in 1
▶ B: String so far has no 11, but ends with a single 1
▶ C: Consecutive 1s have been seen
A B C
0
1
0
1
0,1
56/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 3
Devise an automaton which accepts the language of binary strings
which do not contain 11
What do we need to remember?
▶ A: String so far has no 11, does not end in 1
▶ B: String so far has no 11, but ends with a single 1
▶ C: Consecutive 1s have been seen
A B C
0
1
0
1
0,1
56/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Example 3
Devise an automaton which accepts the language of binary strings
which do not contain 11
What do we need to remember?
▶ A: String so far has no 11, does not end in 1
▶ B: String so far has no 11, but ends with a single 1
▶ C: Consecutive 1s have been seen
A B C
0
1
0
1
0,1
56/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
String in a Language
Let L = {w |w ∈ {0, 1}∗ and w does not contain consecutive 1s}
The following DFA accepts the language L
A B C
0
1
0
1
0,1
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B
▶ Follow transition 0 to reach A
▶ Follow transition 1 to reach B
▶ The result is an accepting state, so 101 is in the language
57/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Error State(s)
An error state is any state from which it is impossible to reach an
accept state. Sometimes we omit these from the diagram. All
missing transitions point to an unseen error state.
You must write “error states not shown” if you omit them.
These DFA are equivalent and both have two states
start error
0
1
0,1
start
0
(error states not shown)
58/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
???
With only one state, q0, how many different finite automata can
you devise?
59/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
outline
▶ Lambda Calculus
▶ Concepts (Operators, FV, Reductions)
▶ Recursion (fixed point, using it)
▶ β-equivalence
▶ Computational power
▶ Functional Programming
▶ Automata Theory
▶ Background, concepts
▶ DFA
▶ Regular languages
▶ NFA
60/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Non deterministic Finite Automata (NFA)
DFA
▶ has exactly one transition per input from each state
▶ no choice in the computation =⇒ deterministic
NFA
▶ can have any number of transitions per input from each state
▶ so some steps of the computation might be non-deterministic
▶ can also have ε-transitions, i.e. transitions which the
automaton can follow without scanning any input
61/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Non deterministic Finite Automata (NFA)
Two examples of NFA which accept the language:
L(M ) = {w |w ∈ {0, 1}∗ and w ends in 1}
q0 q1
0,1
1
q0 q1
0
1
ε
62/63
Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Review
▶ Lambda Calculus
▶ Revision
▶ Computational power
▶ Automata Theory
▶ DFA
▶ Formal definition
▶ DFA diagrams
▶ Using a DFA to do pattern matching
▶ Language of a DFA
▶ Building a DFA
▶ Regular languages
▶ Definition
▶ How to prove that a language is regular
▶ Introduction to NFA
63/63
Lambda Calculus
review
-equivalence
power of
functional programming
Background
Background
FSA
outline
introductory example
DFA
DFA example
Definition
Defining DFA
Regular Languages
Language
More DFA
Designing DFA
error states
NFA
NFA
Review
review