COMP3161/COMP9164
Preliminaries Exercises
Liam O’ 26, 2019
1. Strange Loops: The following system, based on a system called Miu, is perhaps famously mentioned in ’s book, G ̈odel, Escher, Bach.
1 xI Miu 2 3 xII 4 xU 5 xIU Miu x xy I Miu
(a) [⋆] Is MUII Miu derivable? If so, show the derivation tree. If not, explain why not.
MII Miu 3 MIIII Miu
MIIIIIIII IIIIIIIIU Miu
MIIIIIUU IIIII Miu
(b) [⋆⋆] Is xIU Miu admissible? Is it derivable? Justify your answer. xI Miu
Solution: It is not derivable, but it is admissible. It is not derivable because there is no way to construct a tree that looks like this:
I believe it is, however, admissible because it does not change the language Miu. I think there is no string x that could be judged x Miu with this rule that could not be so judged without it, although I welcome any counterexample or proof.
(c) [⋆⋆⋆⋆] Perhaps famously, MU Miu is not admissible. Prove this using rule induction. Hint: Try proving something related to the number of Is in the string.
Solution: We will prove that the number of Is in any string in Miu is not divisible by three. Seeing as MU has zero Is (a multiple of three), if we prove the above, we prove that MU is not admissible.
Base Case (From rule 1). We see that the string MI has only one I, which is not a multiple of three, hence we have shown our goal.
Inductive case (From rule 2). Given that the number of Is in xI is not divisible by three (our inductive hypothesis), we can easily see that the number of Is in xIU is identical and therefore is similarly not divisible by three.
Inductive case (From rule 3). Let n be the number of Is in Mx. Our inductive hypothesis is that 3 n. The number of Is in Mxx, clearly 2n, is similarly indivisible, i.e 3 n =⇒ 3 2n.
Inductive case (From rule 4). Let n be the number of Is in xIIIy. Our inductive hypothesis is that 3 n. The number of Is in xUy, clearly n−3, is similarly indivisible, i.e 3 n =⇒ 3 (n−3) Inductive case (From rule 5). Given that the number of Is in xUUy is the same as the number of Is in xy, our inductive hypothesis trivially proves our goal.
Thus, by induction, no string in Miu has a number of Is divisible by three. Therefore, MU Miu is not admissible.
(d) Here is another language, which we’ll call Mi:
A Mx Mi B xIIIIIIy MiC Mxx Mi xy Mi
i. [⋆⋆⋆] Prove using rule induction that all strings in Mi could be expressed as follows, for some k
and some i, where 2k − 6i > 0 (where Cn is the character C repeated n times): M I2k −6i
Basecase(FromruleA). MI=MI2k−6i when2k−6i=1,i.ewhenk=0andi=0.
Inductive case (From rule B) Given that Mx = MI2a−6b (our inductive hypothesis), we must show that Mxx = M I2k−6i for some k and some i. As x = I2a−6b (from I.H), it is easy to see thatxx=I2(2a−6b) =I2a+1−6(2b) =I2k−6i fork=a+1andi=2b.
Inductive case (from rule C) Given that xIIIIIIy = M I2a−6b (our inductive hypothesis). We must show that xy = M I2k −6i for some k and i. It should be clear to see that this rule simply subtracts six I characters, and therefore xy = MI2a−6(b+1), hence k = a and i = b + 1.
Thus, all strings in Mi can be expressed as M I2k −6i where 2k − 6i > 0
ii. We will now prove the opposite claim that, for all k and i, assuming 2k − 6i > 0: MI2k−6i Mi
To prove this we will need a few lemmas which we will prove separately.
α) [⋆⋆] Prove, using induction on the natural number k (i.e when k = 0 and when k = k′ + 1),
2k thatMI Mi
Base case (when k = 0). We have to show MI Mi, which is true by rule A.
Inductive case (when k = k + 1) We have to show MI Mi, with the inductive hypoth-
esis that MI
2k′ 2k′ Mi. Equivalently, we have to show MI I
2k′ I.H MI Mi B
Mi, as follows:
Therefore, by induction on the natural number k, we have shown ∀k.M I
β) [⋆⋆] Prove, using induction on the natural number i, that M Ik Mi implies M Ik−6i Mi, assuming k − 6i > 0.
Base case (when i = 0). We must show that M Ik Mi implies M Ik−0 Mi, which is obvi- ously a tautology.
Inductive case (when i = i′ + 1) We must show that M Ik Mi implies M Ik−6(i′+1) Mi,
MIIIIII Ik−6(i′+1) Mi due to our assumption that k − 6(i′ + 1) > 0. With this, we can
given the inductive hypothesis that M I prove our goal as shown:
Mi. Note that our I.H can be restated as
k−6(i′+1) I.H MIIIIIII Mi C
M Ik−6(i′+1) Mi Therefore, our goal is shown by induction.
for all k and all i where 2k − 6i > 0 by modus ponens.
Hence, as we know M I
Mi for all k from lemma α, we can conclude from lemma β that M I
These two parts prove that the language Mi is exactly characterised by the formulation M I2k −6i where 2k − 6i > 0. A very useful result!
iii. [⋆] Hence prove or disprove that the following rule is admissible in Mi: Mxx Mi
Mx Mi Lem1
iv. [⋆] Why is the following rule not admissible in Mi? xy Mi
xIIIIIIy MiLem2
v. [⋆⋆⋆] Prove that, for all s, s Mi =⇒ s Miu. Note that using straightforward rule induction appears to necessitate Lem2 above, which we know is not admissible. Try proving using the characterisation we have already developed.
Solution: We know from part i that Mxx Mi =⇒ x2 = I2k−6i for some k and some i where 2k −6i>0.
This rule is not admissible as it adds strings to the language. As 24 − 6 = 10, we know MI10 is in the language. This rule would make MI5 a string in the language which it is not as there is no k and i such that 2k − 6i = 5.
Solution: The rule is not admissible as it adds strings to the language. This allows us to add six I characters to any string in Mi and judge it in Mi, which results in additional strings. For example, applying the rule to MI (which is in Mi), gives us M I7, when our existing formulation of Mi (M I2k−6i) clearly only allows for even amounts of Is.
Solution: We shall show that all strings in Mi, characterised by M I2k −6i where 2k − 6i > 0, are also in Miu. That is, we shall show that M I2k −6i Miu.
Base case (Where k = 0). We must show MI Miu, which we know trivially from rule 1.
To start, we shall prove inductively on k that M I ′
Miu for all k.
2k′+1 Miu. Note we can restate our proof goal as M I
2k′ I.H MI Miu B
Next we must prove that M Ik Miu implies M Ik−6i Miu for all i, assuming k − 6i > 0.
Inductive case (where k = k + 1). We must show M I
Miu, given the inductive hypothesis
Thus we have shown by induction that M I
Miu for all k.
Base case (where i = 0), we must show that M Ik Miu implies M Ik−0 Miu, which is trivially
a tautology.
Inductive case (where i = i′ + 1) we must show that M Ik−6(i′+1) Miu given the inductive
Miu. As we know k − 6(i + 1) > 0, we can restate our inductive hypothesis
hypothesis M I
as MIIIIII Ik−6(i′+1) Miu, and easily prove our goal:
k−6(i′+1) I.H Miu
MUIII Ik−6(i′+1) Miu
MUU Ik−6(i′+1) Ik−6(i′+1) , by modus ponens we can see that MI2k−6i Miu for all k and i where 2k −6i > 0. As this is the exact characterisation of Mi, we have proven that s Mi =⇒ s Miu for all s.
2. Counting Sticks: The following language (also presented in a similar form by , but the original invention is not his) is called the ΦΨ system. Unlike the Miu language discussed above, this language is not comprised of a single judgement, but of a ternary relation, written x Φ y Ψ z, where x, y and z are strings of hyphens (i.e ‘-’), which may be empty (ε). The system is defined as follows:
(a) [⋆] Prove that — Φ — Ψ —–.
B xΦyΨz I -x Φ y Ψ -z
ε Φ — Ψ —B – Φ — Ψ —- I
— Φ — Ψ —–I
(b) [⋆] Is the following rule admissible? Is it derivable? Explain your answer -x Φ y Ψ -zI′
(c) [⋆⋆] Show that x Φ ε Ψ x, for all hyphen strings x, by doing induction on the length of the hyphen string (where x = ε and x = -x′).
(d) [⋆⋆⋆] Showthatif-xΦyΨzthenxΦ-yΨz,forallhyphenstringsx,yandz,bydoinginduction on the size of x.
Solution: It is not derivable (as it cannot be shown with a proof tree), but it is admissible. We know this because the language definition for ΦΨ is unambiguous, so the only way for -x Φ y Ψ -z to hold is if this was established by rule I. Therefore, we can deduce that x Φ y Ψ z, as this is the premise of rule I. We can often “flip” or invert rules in this way, but only if the language definition is unambiguous.
Base case (where x = ε). We must show that ε Φ ε Ψ ε, which is trivially true by rule B. Inductive case (where x = -x′) We have the inductive hypothesis x′ Φ ε Ψ x′, and must show that -x′ Φ ε Ψ -x′. Our goal trivially reduces to our induction hypothesis by rule I.
Therefore we have shown x Φ ε Ψ x for all x by induction on x.
Solution: We shall do induction on x where we keep y and z as arbitrary.
Base case. (where x = ε). We must show that if – Φ y Ψ z then ε Φ -y Ψ z. Observe that the onlywayfor-ΦyΨztoholdisifz=-y. ThereforewemustshowthatεΦ-yΨ-ywhichis true by rule B.
Inductive case. (From rule I, where x = -x′). We have the inductive hypothesis that -x′ Φ y′ Ψ z′ implies x′ Φ -y′ Ψ z′ for any y′, z′.
Wemustshowthat–x′ ΦyΨzimplies-x′ Φ-yΨz. Observethattheonlywaythat–x′ ΦyΨz could hold is if z = -k for some k, then by the rule I′ which we have already shown to be admissible, we know that -x′ Φ y Ψ k. Using our induction hypothesis where y′ = y and z′ = k, we can
establish that x′ Φ -y Ψ k, and therefore by rule I we can finally conclude that -x′ Φ -y Ψ -k as required.
(e) [⋆⋆] ShowthatxΦyΨzimpliesyΦxΨz.
Solution: We show this by rule induction on the premise with the rules of ΦΨ.
Basecase. (FromruleB,whereεΦyΨy). WemustshowthatyΦεΨy. Weprovedthis,most
fortunately, above in part (c).
Inductive case. (From rule I, where -x′ Φ y Ψ −z′ ). We have the inductive hypothesis that
y Φ x′ Ψ z′
yΦ-x′ Ψ-z′ (d)
Thus we have shown by induction that x Φ y Ψ z implies y Φ x Ψ z.
We must show that y Φ -x′ Ψ -z′.
yΦx′ Ψz′I.H -yΦx′Ψ-z′ I
(f) [⋆⋆] Have you figured out what the ΦΨ system actually is? Prove that if -x Φ -y Ψ -z, then z = -x+y (where -x is a hyphen string of length x).
3. Ambiguity and Simultaneity: Here is a simple grammar for a functional programming language 1: x∈N e1Expr e2Expr eExpr eExpr
x Expr Var. e1e2 . λe . (e) .
(a) [⋆] Is this grammar ambiguous? If not, explain why not. If so, give an example of an expression that
has multiple parse trees.
Solution: We proceed by rule induction on the premise.
Base case. (From rule B, where -0 Φ -y Ψ -y), we must show that 0+y = y, which holds trivially. Inductive case (From rule I, where -x′+1 Φ -y Ψ -z′+1), we have the inductive hypothesis that z′ = x′ +y. We must show that z′ +1 = (x′ +1)+y, or, equivalently, that z′ = x′ +y, which is just our I.H.
Thus we have shown by rule induction that the ΦΨ system is in fact unary addition.
Solution: Yes, the expression 1 2 3 could be parsed two different ways, i.e:
1 Expr Var. 2 Expr Var.
3 Expr Var.
1 2 3 Expr
2 Expr Var. 3 Expr Var.
2 3 Expr 1 2 3 Expr
1 Expr Var.
1if you’re interested, it’s called lambda calculus, with de Bruijn indices syntax, not that it’s relevant to the question!
(b) [⋆⋆] Develop a new (unambiguous) grammar that encodes the left associativity of application, that is 1 2 3 4 should be parsed as ((1 2) 3) 4 (modulo parentheses). Furthermore, lambda expressions should extend as far as possible, i.e λ1 2 is equivalent to λ(1 2) not (λ1)2.
(c) [⋆⋆⋆] Prove that all expressions in your grammar are representable in Expr, that is, that your grammar describes only strings that are in Expr.
x∈N e1 PExpr e2 AExpr eLExpr
x AExpr AVar. e1e2 PExpr AAppl. λe LExpr AAbs.
e LExpr AParen.y e PExpr Shunt e AExpr Shunt (e) AExpr e LExpr 1 e PExpr 2
Solution: We shall prove the following simultaneously: • xLExpr ⇒xExpr
• xPExpr ⇒xExpr
• xAExpr ⇒xExpr
Proof. Base case (From rule AVar., where x AExpr for some x ∈ N). We must show x Expr, trivial by rule Var.
Inductive case. (From rule AAppl., where e1 e2 PExpr ). We know e1 PExpr , and e2 AExpr which give rise to inductive hypotheses e1 Expr (I.H1) and e2 Expr (I.H2). We must show that e1e2 Expr.
e1 Expr IH1 e2 Expr IH2 e1e2 Expr
Inductive case. (From rule AAbs., where λx LExpr). We know that x LExpr, giving inductive hypothesis x Expr. The rule Abs. then proves our goal: λx Expr.
Inductive case. (From rule AParen., where (x) AExpr). We know that x LExpr, giving inductive hypothesis x Expr. Then by rule Paren. we show our goal (x) Expr.
The inductive case for the rules Shunt1 and Shunt2 are trivial as they do not alter the expression.
Thus, by induction, s LExpr ∨ s PExpr ∨ s AExpr =⇒ s Expr . We can state this more succinctly thanks to the Shunt rules as s LExpr =⇒ s Expr.
4. Regular Expressions: Consider this language used to describe regular expressions consisting of:
• single characters, written c
• Sequential composition, written R; R
• Nondeterministic choice, written R | R. • Kleene star, written R⋆.
• Grouping parentheses.
cChar aR bR aR bR aR aR c R a; b R a | b R a ⋆ R (a) R
(a) [⋆] In what way is this grammar ambiguous? Identify an expression with multiple parse trees.
Solution: Precedence between choice and sequential composition is not enforced, and the asso- ciativity of the two binary operators is not clarified either.
a; b | c | d encounters both the precedence and the associativity issue.
(b) [⋆] Devise an alternative grammar that is unambiguous, order of operations should be such that a;b;c⋆ |a;d|e
is parsed with the grouping indicated by the parentheses in: (a; (b; (c⋆))) | ((a; d) | e)
c Char a RAtom b RSeq a RSeq b RChoice a RAtom a RChoice
c RAtom a;b RSeq
a | b RChoice a⋆RAtom (a) RAtom a RAtom a RSeq
a RSeq a RChoice
5. Key Combinations: Consider the language used to document key combinations:
x ∈ {a,b,…,Shift}Key c1 K c2 KHold c1 K c2 KThen x K c1&c2K c1c2K
For example Ctrl & C is a string in this language. (a) [⋆] Find an example of ambiguity in this language.
c K Paren (c)K
Solution: The very next question offers an example: qw&ert
This can be parsed using Hold first or using Then first. It also shows an associativity issue with the Then rule.
(b) [⋆] Eliminate ambiguity such that
is parsed with this grouping:
and such that
is parsed with the following grouping:
qw&ert ( q (( w & e )( r
t ))) Ctrl & Shift⇑ & Q
( Ctrl & Shift ⇑ )& Q
x ∈ {a,b,…,Shift}Key c1 KH c2 KAHold c1 KH c2 KTThen c KT Paren
x KA c1&c2 KH
aKA aKH aKH aKT
c1c2 KT (c) KA