School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 10
4–8 October 2021
Content: pushdown automata, context-free grammars, closure results for context-free lan- guages, the pumping lemma for context-free languages
The exercises
T10.1 Construct push-down automata (PDAs) for the following languages. In each case, the alpha- bet is Σ = {a,b}.
(i) {aibaj |i>j≥0} (ii) {w|wisapalindrome} Continued in P10.1 & P10.2
T10.2 A PDA (Q,Σ,Γ,δ,q0,F) is progressive iff δ(q,ǫ,a) = ∅, for every q ∈ Q and a ∈ Γǫ. That is, a progressive PDA consumes an input symbol in each of its transitions.
A PDA is deterministic if, from any configuration, it has at most one available move. That is,
∀q ∈ Q ∀v ∈ Σ ∀a ∈ Γ|δ(q, v, a)| + |δ(q, v, ǫ)| + |δ(q, ǫ, a)| + |δ(q, ǫ, ǫ)| ≤ 1
Which of your PDAs from the previous question are progressive, and which are deterministic?
(The PDAs required in Assignment 2’s Challenge 6 are both progressive and deterministic.)
T10.3 (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 that B is not context-free by doing what we did to prove that A is not context-free. Where does the attempted proof fail?
T10.4 Show that the class of context-free languages is closed under the regular operations: union, concatenation, and Kleene star. Hint: Show how context-free grammars for A and B can be manipulated to produce context-free grammars for A ∪ B, AB, and A∗. Careful: The variables used in the grammars for A and in B could overlap.
Continued in P10.3