当前位置:天才代写 > 作业代写 > Theory of Computation1代写 Homework代写 course代写

Theory of Computation1代写 Homework代写 course代写

2021-04-11 12:00 星期日 所属: 作业代写 浏览:84

Theory of Computation1代写

CSCI 383: Theory of Computation Spring 2019

Theory of Computation1代写 Questions: Select any one part to be handed in at the beginning of class on Monday, April 15. Hand in the remaining parts

Homework 7

One part due April 15, two parts April 17

Reading: Kozen, Sections 27, 28, 29, and 30  Theory of Computation1代写

Questions: Select any one part to be handed in at the beginning of class on Monday, April 15. Hand in the remaining parts on Wednesday, April 17. 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.

Theory of Computation1代写
Theory of Computation1代写

Part 1: Public Display of Aggression Theory of Computation1代写

a.Give an NPDA for L = {anbn+mcm}. You  may  choose to accept byfinal state or empty stack. No formal proof required, but give a clear, concise

b.Inyour 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 toaccept acbbbcc.

Part 2: osure Theory of Computation1代写

Show using PDAs that if A is a context-free language, then

Suff ix(A) = {v | uv A for some string u Σ}

is also context-free. In other words, you should:

  • Informallydescribe a procedure for turning an NPDA for A into an NPDA for Suff ix(A).
  • Formally specify your procedure.
  • Prove that your construction is correct.

Part 3: Double Trouble Theory of Computation1代写

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 Σ  {s}, 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.Theory of Computation1代写

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.

Theory of Computation1代写
Theory of Computation1代写

其他代写:algorithm代写 analysis代写 app代写 assembly代写 assignment代写 C++代写 code代写 course代写 dataset代写 java代写 web代写 北美作业代写 编程代写 考试助攻 program代写 cs作业代写

合作平台:essay代写 论文代写 写手招聘 英国留学生代写

 

天才代写-代写联系方式