The plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 11
21–23 October 2020
Try to get through all of this week’s exercises. Reminder 1: A good text on context-free languages is available under “Readings Online”. Reminder 2: Assignment 2 is due by the end of Week 11.
The exercises
90. Construct push-down automata (PDAs) for the languages from Exercise 77. In each case, the alphabet is Σ = {0, 1}.
(a) {w | w starts and ends with the same symbol} (b) {w | the length of w is odd}
(c) {w | the length of w is odd and its middle symbol is 0} (d) {w | w is a palindrome}
91. Let us say that a PDA (Q,Σ,Γ,δ,q0,F) is progressive if none of its transitions are of form δ(q, ε, a) = . . .. That is, a progressive PDA consumes an input symbol in each of its moves.
Let us say that a PDA is deterministic if, from any configuration, it has at most one available move. That is,
(a) ∀q∈Q∀v∈Σ∪{ε}∀a∈Γ∪{ε}(|δ(q,v,a)|≤1)
(b) ∀q∈Q∀a∈Γ∪{ε}(|δ(q,ε,a)|=1⇒∀v∈Σ(|δ(q,v,a)|=0)) (c) ∀q∈Q∀v∈Σ∪{ε}(|δ(q,v,ε)|=1⇒∀a∈Γ(|δ(q,v,a)|=0))
Which of your PDAs from Exercise 90 are progressive, and which are deterministic?
(The PDAs required in Assignment 2’s Challenge 6 are both progressive and deterministic.)
92. We have seen that the set of context-free languages is not closed under intersection. However, it is closed under intersection with regular languages. That is, if L is context-free and R is regular then L ∩ R is context-free.
We can show this if we can show how to construct a push-down automaton P ′ for L ∩ R from a push-down automaton P for L and a DFA D for R. The idea is that we can do something similar to what we did in Exercise 65 when we built “product automata”, that is, DFAs for languages R1 ∩ R2 where R1 and R2 were regular languages. If P has state set QP and D has state set QD, then P′ will have state set QP × QD.
More precisely, let P = (QP,Σ,Γ,δP,qP,FP) and let D = (QD,Σ,δD,qD,FD). Recall the types of the transition functions:
δP :(QP ×Σε×Γε)→P(QP ×Γε) δD :(QD ×Σ)→QD
WeconstructP′ withthefollowingcomponents: P′ =(QP ×QD,Σ,Γ,δ,(qP,qD),FP ×FD). Discuss how P′ can be constructed from P and D. Then give a formal definition of δ, the transition function for P′.
93. (a) Consider the language A = {aibjaibj | i ≥ 0 ∧ j ≥ 0}. Use the pumping lemma for context-free languages to show that A is not context-free.
(b) Now consider B = {aibjajbi | i ≥ 0 ∧ j ≥ 0}. Give a context-free grammar for B.
(c) A and B look very similar. We might try to prove B not context-free by doing what we
did to prove that A is not context-free. Where does the attempted proof fail?
94. Recall that a binary relation ≺ over set S is a well-founded relation iff there is no infinite sequence s0, s1, s2, s3, . . . such that si ≻ si+1 for all i ∈ N. That is, each sequence of elements from S, when listed in decreasing order, is finite. For each of the following, say whether it is well-founded:
(a) The usual “smaller than” relation, <, on the natural numbers N.
(b) The usual “smaller than” relation, <, on the rational numbers, Q. x
(c) The relation “is a proper sublist of” on the set of finite lists.
(d) The (strict) lexicographic ordering of pairs of natural numbers, that is, the relation ≺
definedby(m,m′)≺(n,n′)iffm
that you never run out. Now repeat the following process:
(a) If the bag contains at most one marble, halt; otherwise remove two marbles from the bag (without looking).
(b) If one of the two marbles is red, move both to the box.
(c) If both are white, put one of them back into the bag, together with 5 blue marbles from the box (the other white marble goes in the box).
(d) Otherwise move both to the box, and move 10 red marbles from the box to the bag.
Show that the process must halt.
96. (Optional.) The Week 10 lecture introduced the function c : N → N, defined recursively like
so:
1 i f n = 0 o r n = 1
c(n) = c(n/2) if n is even and n > 1
c(3n+1) ifnisoddandn>1
Write a Haskell function hailstone :: Integer -> Int which calculates the number of recursive calls made when computing c(n). For example, hailstone 5 should evaluate to 5, and hailstone 27 should evaluate to 111.
c is known to terminate for all natural numbers up to 1020. It is conjectured to terminate for all n ∈ N, but whether this is is actually the case is an open problem. There are examples where similar conjectures have been refuted. One famous example has to do with prime factorisations. Say that n > 1 is peven if its prime factorisation has an even number of factors; otherwise n is podd. So 28 = 2·2·7 is podd, and 40 = 2·2·2·5 is peven. P ́olya conjectured that, for any k, the set {2,3,4,…,k} never has a majority of peven elements. However, that turned out to be false, the smallest counter-example being k = 906150257.