FOUNDATIONS OF COMPUTATION 2014
PROBLEM SHEET 4
ANSWERS AND SELECTED SOLUTIONS
ISSUED DECEMBER 2014
1. [5/25 marks] Describe the language accepted by the following pushdown automaton (where the input alphabet is {a, b}, s is the initial state and f is the unique
final state).
(s, a, e), (s, a)
(s, b, a), (f, e)
(f, b, a), (f, e)
(f, a, a), (f, e)
Answer.
{an bw| w ∈ {a, b}∗ , |w| = n − 1}.
2. [5/25 marks] Construct pushdown automata accepting the following languages.
(i) {am b2m ∈ {a, b}∗ | m ≥ 0}
Answer.
(s, e, e), (f, e)
(s, a, e), (s, aa)
(s, b, a), (f, e)
(f, b, a)(f, e)
(ii) {ak bk ci ∈ {a, b, c}∗ | k ≥ 0, i ≥ 0}
Answer. One method of producing the answer would be first to write out
a context-free grammar generating the language, and then to translate this
grammar into the description of an automaton using the algorithm form
Lecture Notes.
3. [5/25 marks] Prove that the following languages are not context-free.
(i) {a3k b2k ck ∈ {a, b, c}∗ | k ≥ 0}
Suppose, contrary to our claim, that this language (denote it by L) is
context-free. Applying the Pumping Lemma to L we get the number n.
Consider the word w = a3n b2n cn having the length 6n > n. Then, by the
Pumping Lemma, w is representable in a form w = uvxyz. Since |vxy| ≤ n,
the word vxy contains at most two different letters from {a, b, c}. For definiteness, let these be a, b (could be just a or just b). Since |vy| > 0, either
v or y contains at least one letter (either a or b). Let, for definiteness, it
be b in the subword y. By the Pumping Lemma, w′ = uv 2 xy 2 z ∈ L. So
y 2 contains more b’s than y, thus the number of b’s have increased in w′
as compared to w. But the number of c’s remains the same in w′ because
vxy does not contain c’s. It follows that w′ is not of the form a3i b2i ci , i.e.,
w′ ̸∈ L which is a contradiction.
1
2
ISSUED DECEMBER 2014
(ii) {abk abk abk ∈ {a, b}∗ | k ≥ 0}
Standard application of Pumping Lemma for context-free languages.
(iii) {ak+m bk am bk ∈ {a, b}∗ | k ≥ 0, m ≥ 0}
Standard application of Pumping Lemma for context-free languages.
4. [5/25 marks] Describe formally (i.e., by means of a transition function) a Turing
machine which decides whether the input word an ∈ {a}∗ has an even or an odd
length.
Assume that the input word is written on the tape immediately to the right of the
symbol ◃. Assume also that the machine terminates with the halting state e if the
length of the input is even, and with the halting state o if the length of the input is
odd. The machine has also two non-halting states, s (initial) and q. The transition
function may be defined as follows.
s a (q, →)
s ⊔ (e, ⊔)
q a (s, →)
q ⊔ (o, ⊔)
5. [5/25 marks] For two decidable languages L1 and L2 , let M1 and M2 be the
Turing machines that decide them. The following is a Turing machine M ′ that
decides the union of L1 and L2 :
On input w:
(1) Run M1 on w. If it accepts, accept. Otherwise, go to (2).
(2) Run M2 on w. If it accepts, accept. Otherwise, reject.
M ′ accepts w if either M1 or M2 accepts it. If both reject, M ′
rejects.
Using this description as a template, show that the collection of all decidable
languages is closed under the operation of:
(i) intersection,
Trivial.
(ii) complement,
Trivial.
(iii) concatenation,
Consider all possible splittings of the input word w into two parts. For each
splitting w = w1 w2 , run M1 on w1 . If it rejects, go to the next splitting.
Otherwise, run M2 on w2 . If it accepts, accept. Otherwise, go to the next
splitting. If, in either case, “next splitting” does not exist, reject.
(iv) Kleene star.
The idea of a solution is similar to the case of concatenation, except that the
machine considers all possible splittings of the input word into all possible
parts.
© Copyright 2024 ExpyDoc
