COMP3161/COMP9164
Preliminaries Exercises
Liam O’Connor September 27, 2019
1. Strange Loops: The following system, based on a system called Miu, is perhaps famously mentioned in Douglas Hofstadter’s book, G ̈odel, Escher, Bach.
1 xI Miu 2 Mx Miu 3 xIIIy Miu4 xUUy Miu5 xIU Miu Mxx Miu xUy Miu xy Miu
MI Miu
(a) [⋆] Is MUII Miu derivable? If so, show the derivation tree. If not, explain why not.
(b) [⋆⋆] Is xIU Miu admissible? Is it derivable? Justify your answer. xI Miu
(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.
(d) Here is another language, which we’ll call Mi:
A Mx Mi B xIIIIIIy MiC Mxx Mi xy Mi
MI 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
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
β) [⋆⋆] Prove, using induction on the natural number i, that M Ik Mi implies M Ik−6i Mi, assuming k − 6i > 0.
2k
for all k and all i where 2k − 6i > 0 by modus ponens.
2k −6i
Hence, as we know M I
Mi for all k from lemma α, we can conclude from lemma β that M I
Mi
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.
1
2. Counting Sticks: The following language (also presented in a similar form by Douglas Hofstadter, 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:
ε Φ x Ψ x
B xΦyΨz I -x Φ y Ψ -z
(a) [⋆] Prove that — Φ — Ψ —–.
(b) [⋆] Is the following rule admissible? Is it derivable? Explain your answer
-x Φ y Ψ -zI′ xΦyΨz
(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.
(e) [⋆⋆] ShowthatxΦyΨzimpliesyΦxΨz.
(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 Expr Appl. λe Expr Abst. (e) Expr Paren.
(a) [⋆] Is this grammar ambiguous? If not, explain why not. If so, give an example of an expression that has multiple parse trees.
(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.
4. Regular Expressions: Consider this language used to describe regular expressions consisting of:
• • • • •
(a) (b)
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
[⋆] In what way is this grammar ambiguous? Identify an expression with multiple parse trees. [⋆] 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)
1if you’re interested, it’s called lambda calculus, with de Bruijn indices syntax, not that it’s relevant to the question!
Page 2
5. Key Combinations: Consider the language used to document key combinations:
x ∈ {a,b,…,Shift}Key c1 K c2 KHold K c1&c2 K
For example & is a string in this language.
(a) [⋆] Find an example of ambiguity in this language.
(b) [⋆] Eliminate ambiguity such that
c1 K c2 KThen c1c2 K
c K Paren (c) K
x
Ctrl
C
is parsed with this grouping:
and such that
is parsed with the following grouping:
&
( (( & )( )))
&&
( & )&
q
w
e
r
t
q
w
e
r
t
Ctrl
Page 3
Shift ⇑
Q
Ctrl
Shift ⇑
Q