代写 data structure algorithm Java lisp Lambda Calculus COMP2022: Formal Languages and Logic

COMP2022: Formal Languages and Logic
2018, Semester 2, Week 6
Joseph Godbehere
6th September, 2018

COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING
This material has been reproduced and communicated to you by or on behalf of the University of Sydney pursuant to part VB of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any further copying or communication of this material by you may be subject of copyright protect under the Act.
Do not remove this notice.

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Outline
▶ Regular Expressions
▶ Equivalence of FA and Regular Expressions
▶ Proving if a language is, or is not, regular
3/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Equivalence of RegEx and FA
Theorem:
A language is regular if and only if a regular expression describes it.
Proof:
Show the equivalence of RegEx and FA (RegEx ⇔ FA)
1. RegEx ⇒ FA:
Show that for each RegEx, there exists an NFA which recognises the same language
2. FA ⇒ RegEx:
Show that for each NFA, there exists a RegEx which recognises the same language
5/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
From RegEx to FA: atomic cases
Automaton for ∅
Automaton for ε
Automaton for x ∈ Σ x
6/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
NFA for regular operations: Union
Let M1 and M2 be automata recognising L(R1) and L(R2) Then an automaton M for R1 | R2 is:
q1 ε
q0
ε
M1 M2
q2
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:
M1 ∈F M2 1ε
q1 ∈ F1 ε q2
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 R1⋆ is:
ε
q0 ε q1
ε
M1
9/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example: a | bc⋆: from RegEx to NFA
1. Construct automata for the atomic regular expressions a, b, c 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
From NFA to RegEx: Simple examples
This automaton gives the RegEx x x
Thisonegives(a|b|…|Y |Z)⋆.pdf a…z,A…Z
.pdf
14/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
From NFA to RegEx: Simple examples
A more complex one:
10
01
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.
a | bb bc
q2 ε qa
aa⋆
qs ε q1
∅∅∅
{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.
a | bb
qs ε q1 bc q2 ε qa
aa⋆
We do not show the ∅ transitions (why not?) {abc, abca, abcbb, aaaaaabc} ⊆ L
17/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Converting an NFA to a GNFA
Create a new non-accepting start state qs , with a ε-transition to the original start state.
Create a new accept state qa with ε-transitions from the original accept states, which are no longer accepting.
Label the transitions between every ordered pair (qi , qj ) of states from the NFA as the union of the atomic RegEx describing each transition from qi to qj in the NFA.
q1 a qs ε q1 a
bb
q2 a,b qa ε q2 a|b 18/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Simple example: eliminate state q1
a|b
qs ε q1 b q2 ε qa
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
a|b
qs a⋆b q2 ε qa
a
19/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Simple example: eliminate state q2 a|b
qs a⋆b q2 ε qa
There is only one way to pass through q2:
qs →q2 a⋆b q2 → q2 any number of times (a|b)⋆
q2 → qa
a⋆b(a | b)⋆
ε
qs
The language of the original automaton is a⋆b(a | b)⋆
qa
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}
R4
qi
R1
qj R3
qelim
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 = ∅
R2
21/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
01 10
q0 q1 q2
10
Convert to GNFA:
22/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
01 10
q0 q1 q2
10
Convert to GNFA:
q01q01 s1
ε
q0 1 0 q2 ε
qa
22/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
ε
01 10
q0 q1 q2
ε10
qa
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|∅
▶ (qs,qa):
▶ (q1,q1):
▶ (q1,qa):
23/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
ε
01 10
q0 q1 q2
ε10
qa
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):
23/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
ε
01 10
q0 q1 q2
ε10
qa
We can eliminate the states in any order. Eliminate q0.
All pairs of states with transitions which are not ∅ through q0:
▶ (qs,q1):R1 =ε,R2 =0,R3 =1,R4 =∅⇒ε0⋆1|∅=0⋆1 ▶ (qs,qa):R1 =ε,R2 =0,R3 =ε,R4 =∅⇒ε0⋆ε|∅=0⋆
▶ (q1,q1):R1 =1,R2 =0,R3 =1,R4 =∅⇒10⋆1|∅=10⋆1 ▶ (q1,qa):R1 =1,R2 =0,R3 =ε,R4 =∅⇒10⋆ε|∅=10⋆
23/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
0⋆ 0⋆1
10⋆1
q1
0
0
1
q2
10⋆
We can eliminate the states in any order. Eliminate q2.
qa
All pairs of states with transitions which are not ∅ through q2: ▶
24/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
0⋆ 0⋆1
01⋆0 | 10⋆1
q1
10⋆
There is only q1 left to remove.
All pairs of states with transitions which are not ∅ through q1: ▶ (qs,qa):R1 =0⋆1,
qa
25/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 2: divisible by 3
qs
0⋆1(01⋆0 | 10⋆1)⋆10⋆ | 0⋆
qa
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
q1 a
q0
b
q2 As GNFA:
27/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
q1 a
q0
b
q2 As GNFA:
qs ε q0
q1 aε
bε q2
qa
27/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs ε q0
q1 aε
bε q2
qa
Eliminate q2:
28/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs ε q0
q1 aε
bε q2
qa
Eliminate q2:
qs ε q0
q1 aε
b∅⋆ε | ∅ = b
qa
28/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs ε q0 Eliminate q1:
q1 aε
b
qa
29/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qs ε q0 Eliminate q1:
q1 aε
b
qa
a∅⋆ε | b = a | b q s0a
q ε q
29/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qεqa|bq s0a
Eliminate q0:
Simplify, to get the expected:
30/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example 3: Multiple accept states
qεqa|bq s0a
Eliminate q0:
q ε∅⋆(a | b) | ∅ q
sa
Simplify, to get the expected:
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 ▶ Foreachpair(qi,qj)whereqi,qj ∈Q\{qelim}
▶ Replace ▶ R1 ▶ R2 ▶ R3 ▶ R4
arrow qi → qj with ((R1 )(R2 )⋆ (R3 ) | (R4 )), where is the RegEx on transition qi → qelim
is the RegEx on transition qelim → qelim is the RegEx on transition qelim → qj
is the RegEx on transition qi → qj
31/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
33/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Pumping s using y
yQ QQ
f
q0 x qi
z
Suppose some string s exists, passing through M :
▶ From q0 to qi, using a string x, then
▶ from qi back to qi, using a string y ̸= ε, then
▶ from qi to some accept state f ∈ F, using a string z
34/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Long strings in finite automata
yQ QQ
q0 x qi
SupposeM isaDFAwithnstates,ands∈L(M),but|s|>n+1
z
f
35/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Long strings in finite automata
yQ QQ
q0 x qi
SupposeM isaDFAwithnstates,ands∈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.
z
f
35/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Finite automata, infinite languages
All finite languages are regular. (Why?)
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. xykz ∈ 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
39/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn|n ≥ 0} is not regular 1. Assumption: L is regular.
39/62

Outline RegEx ⇒ NFA NFA ⇒ RegEx Proving Regularity Grammars Lambda Calculus Review
Example
Show that L = {anbn|n ≥ 0} is not regular
1. Assumption: L is regular.
2. Then there exists some p ≥ 0 satisfying the pumping lemma. 3. Let s = apbp (note: the same p as above!)
4. |s| ≥ p, therefore we can write s = xyz such that 4.1 xykz∈Lforallk≥0(i.e.wecanpumpy)
4.2 |y|>0 4.3 |xy|≤p
5. Thereforey=ai forsome00 4.3 |xy|≤p
5. Thereforey=ai forsome00 4.3 |xy|≤p
5. Thereforey=ai forsome0 0}, which we already
know is not regular
How does it derive 000111?
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 = {0n 1n | n > 0}, which we already
know is not regular
How does it derive 000111?
S
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 sees the girl, the ball likes the girl, the ball sees the girl,
the girl likes the ball, the girl sees the ball, the ball likes the ball,
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
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
public class Tree {
public public public
public this
final final final
int element ; Tree left ; Tree right ;
Tree(int element , Tree left , Tree right) { . element = element ;
this.left = left;
this . right = right ; }
}
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.(

Related Posts