代写COMP4141 25T1 Homework 4代做Python编程

日期：2025-03-13 05:29

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.)

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 lefthand 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.)