/Users/billy/gits/moc-2021/problem-sets/ps10.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 10
4 – 8 October 2021
Content: pushdown automata, context-free grammars, closure results for context-free lan-
guages
P10.1 Construct a push-down automaton for {w | the length of w is odd and its middle symbol is 0},
over the alphabet Σ = {0, 1}. What’s the minimum number of states you can achieve?
P10.2 Take any context-free grammar in any problem set or tutorial, and construct a pushdown
automata which recognises the language of that grammar. Try using the CFG to PDA
conversion from the lectures, otherwise you can try to understand what the language is, and
construct a PDA from scratch. Repeat this a few times for practice.
P10.3 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
We construct P ′ with the following components: 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 ′.
P10.4 Give a context-free grammar for {aibjck | i = j ∨ j = k where i, j, k ≥ 0}. Is your grammar
ambiguous? Why or why not?
P10.5 Consider the context-free grammar G = ({S,A,B}, {a, b}, R, S) with rules R:
S → A B A
A → a A | ǫ
B → b B | ǫ
(a) Show that G is ambiguous.
(b) The language generated by G is regular; give a regular expression for L(G).
(c) Give an unambiguous context-free grammar, equivalent to G. Hint: As an intermediate
step, you may want to build a DFA for L(G).
P10.6 Give a context-free grammar for the language recognised by this DFA:
1 2
34
a
b ba
a
ba, b