代写 game Java math python Lambda Calculus COMP2022: Formal Languages and Logic

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
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.
WesayF hasafixedpointif∃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=YH
13/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
()
H = λfxyz .(condition)(base case)(recursive case calls f ) F=YH
Evaluation:
F a b c = (Y H ) a b c
=H (Y H)abc (YH isafixedpointofH)
()
= λ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 ▶ Basecasen=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
F3abc
= 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
()
=…=(ISZERO3)NIL λe.(YH)(CONSeNIL)(PRED3) abc ()
=…=FALSENIL λe.(YH)(CONSeNIL)(PRED3) abc ()
=…= λe.(YH)(CONSeNIL)(PRED3) abc = … = (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 isthesameasN
▶ M ≡N : M isequivalenttoN (hasthesameeffect) ▶ M ↠β N : M β-reducestoN
▶ M →β N : M β-reducestoN (inonestep)
▶ M =β N : M isβ-convertabletoN
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
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
Regular (DFA)
▶ 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)
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
▶ ifx=abεcεdεthen|x|=?
▶ 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
Introductory Example
Σ \ {.} q.qpqdqfq
01234
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
Σ \ {.} q.qpqdqfq
01234
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
Σ \ {.} q.qpqdqfq
01234
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
40/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Introductory Example
Σ \ {.} q.qpqdqfq
01234
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 ‘.’
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:
Σ \ {.} Σ \ {., f }
Σ \ {., d } Σ \ {., p}
q.qpqdqfq 01234
Σ \ {.}
. .
.
.
42/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Alternative notation
You can be more descriptive if you like:
not . not . or f
not . or d not . or p
ends: . other
not .
ends:
.
p
ends:
.p .
.
ends:
.pd
f ends: .pdf
d
. .
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 isgivenby
4. q0 ∈ Q is the start state
5. F = {q1}
Now we can draw M1:
0
1
q0
q0
q1
q1
q2
q1
q2
q1
q1
46/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q =
2. Σ =
3. δ:Q×Σ→Q isgivenby:
4. The start state is:
5. The set of accept states is: F =
Some strings where M2 ends on an accept state are:
q2
0
47/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q={q1,q2}
2. Σ =
3. δ:Q×Σ→Q isgivenby:
4. The start state is:
5. The set of accept states is: F =
Some strings where M2 ends on an accept state are:
q2
0
47/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q={q1,q2}
2. Σ={0,1}
3. δ:Q×Σ→Q isgivenby:
4. The start state is:
5. The set of accept states is: F =
Some strings where M2 ends on an accept state are:
q2
0
47/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q={q1,q2}
2. Σ={0,1}
3. δ:Q×Σ→Q isgivenby:
4. The start state is: q1
5. The set of accept states is: F =
Some strings where M2 ends on an accept state are:
q2
0
0
1
q1
q1
q2
q2
q1
q2
47/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q={q1,q2}
2. Σ={0,1}
3. δ:Q×Σ→Q isgivenby:
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:
q2
0
0
1
q1
q1
q2
q2
q1
q2
47/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Define a DFA from a diagram
01 1
q1
We can formally describe M2 as: 1. Q={q1,q2}
2. Σ={0,1}
3. δ:Q×Σ→Q isgivenby:
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
q2
0
0
1
q1
q1
q2
q2
q1
q2
47/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 fori=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
51/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
What language is accepted by M1? 01
0 q01q1 q2
0,1
52/63

Lambda Calculus Background FSA DFA Regular Languages More DFA NFA Review
Examples of Regular Languages
What language is accepted by M1? 01
0 q01q1 q2
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
01 1
q1
What language is accepted by M2?
q2
0
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
01 1
q1
What language is accepted by M2?
L(M2) = {w|w ends with a 1}
q2
0
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.
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
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:Stringsofarhasno11,doesnotendin1
▶ B: String so far has no 11, but ends with a single 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
0,1
0
1
A B1C
0
Is the string 101 in L?
▶ Start at A
▶ Follow transition 1 to reach B ▶ Follow transition 0 to reach A
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
00,1 0
start 1 error start
(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
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}
0,1
q0 1 q1 0
1
ε
q0
q1
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

Related Posts