Prove or disprove the following statements: (a) Stacks are getting expensive lat

Question

Prove or disprove the following statements: (a) Stacks are getting expensive lately! I limit my PDAs to only have a maximum stack height of 50, and if during a computation the PDA tries to push on a stack with height of 50, the computation terminates. My model of PDAs then still recognizes the context-free languages. (b) The energy it is taking for PDAs to take a transition where it reads off of the input is increasing, so it may be a good idea to allow "breaks" between them. I want every accepting computation of every string to consist of at least 1 epsilon-transition between each character read from the input, without worrying about what happens to the stack. Call these machines epsilon-PDAs. Then epsilon-PDAs still recognize the context-free languages.

Explanation / Answer

a) The given stack has finite height and the stack contains only possible number of finite contents , The size of the stack is h , and has the possible heights of 0<=50<=h , For the k symbols there are 25i=0 ki possibilities . For each possibility we can be any state and read any one input character , In all these transitions the stack contents change , but it will be in any one of the finite possibility , Since all of the possibilities are finite , there can be DFA made , And for every language context-free language recognizes, PDA also recognizes, and vice versa.

b) Consider P as PDA , For reading of every transition insert an -transition each time before and after reading . The states change from q and q' to s1 and s2 from q to s1 and from q' to s2 and the original transition is pasted between s1 and s2 . Therefore there is a -PDA for every CFL and because -PDA is a PDA by definition , They still recognize the context-free languages.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.