代写计算机理论作业。
Questions
Select any one part to be handed in at the beginning of class. Your solutions
must be typeset in LaTeX. Figures may be drawn by hand. Each solution must be
handed in separately. Print front and back. If a single solution requires
multiple pages, staple them. List your collaborators and include the honor
code.
Part 1: Public Display of Aggression
- a. Give an NPDA. You may choose to accept by final state or empty stack. No formal proof required, but give a clear, concise explanation.
- b. In your NPDA give the sequence of transitions you would apply to accept the string abbbcc. (It will help to label your transitions in the previous part.)
- c. Briefly argue that there is no sequence of transitions that would lead your machine to accept acbbbcc.
Part 2: osure
Show using PDAs that if A is a context-free language, then
Suffix(A) = {v | uv ∈ A for some string u ∈ Σ∗}
is also context-free. In other words, you should:
- Informally describe a procedure for turning an NPDA for A into an NPDA for Suffix(A).
- Formally specify your procedure.
- Prove that your construction is correct.
Part 3: Double Trouble
Let’s define a Twin Pushdown Automaton (TPDA) to be like a standard Pushdown
Automaton with two stacks, rather than one. In particular, the transition
function would include transitions of the form
(p,a,A,B) → (q,α,β)
for p, q ∈ Q, a ∈ Σ ∪ {ε}, A, B ∈ Γ and α, β ∈ Γ∗.
Such a rule would mean that while in state p, if the character a is read from
the string, A is top of the first stack, and B is on top of the second stack,
then we can move to state q, pop A and B from their respective stacks, and
push α and β onto the first and second stack respectively. The remainder of
the definition of a TPDA would be analogous to that of a standard PDA.
Acceptance is by final state.
Prove that TPDAs and NPDAs are not equivalent in expressive power. In other
words, find a language L that is not context-free, but for which there exists
a TPDA. You do not need to prove that your TPDA accepts L (though you should
provide a brief explanation and a formal description of your TPDA). You do
need to prove that L is not context-free.
