COMP4141 25T1 Homework 4
March 11, 2025
Task (pass).
Give a context free grammar for the language
{w#x : w ∈ {0, 1}∗ and x = u · rev(w) · v for some u, v ∈ {0, 1}∗}
over the alphabet Σ = {0, 1, #}. Here rev(w) is the reverse of the word w. Explain your answer by
describing the role that each non-terminal plays in this grammar.
Task (pass).
Construct a push-down automaton for the language
{w#x : w ∈ {0, 1}∗ and x = u · rev(w) · v for some u, v ∈ {0, 1}∗}
over the alphabet Σ = {0, 1, #}. Here rev(w) is the reverse of the word w. Explain your answer by
describing the role that each state of the automaton plays, and the behaviour of the stack as the automaton
is processing a word.
Task (credit).
Suppose that L1 and L2 are regular languages over alphabet Σ. Show that the following language is context
free:
L = {xy : x ∈ L1 and y ∈ L2 and |x| = |y|}
Hint: use a push-down automaton.
Task (distinction).
Let L1 be a context-free language and L2 a regular language, both over an alphabet Σ. Show that the
following language is context-free:
L = {w : w ∈ L1 and w has a substring in L2}
(We say u is a substring of w if w = xuy for some words x, y.)
1
Task (hd).
Suppose we generalise pushdown automata to machines that have two stacks. Such a generalized machine
has transitions of the form
q1, a, s1, s2 → t1, t2, q2
where q1, q2 are in the (finite) set of states of the machine, a is in the input alphabet Σ, or a = ϵ, and
s1, s2, t1, t2 ∈ Γ∪ {ϵ}, where Γ is the stack alphabet. Such a transition means that from state q1, on reading
input a, with s1 and s2 at the top of the two stacks, the machine replaces the s1 and s2 at the top of the
stacks by t1 and t2, respectively, and moves to state q2. Like PDA’s these machines are nondeterministic,
so there may be multiple transitions with the same left hand side q1, a, s1, s2.
Show that such two-stack pushdown automata can accept a language that is not context-free. (You may
use one of the languages shown in lectures to be non-context free.)
2

学霸联盟