Register

Ullman (TOC) Edition 3 Exercise 6.2 Question 8 (Page No. 242)

554 views
0 votes
0 votes
A $PDA$ is called restricted if on any transition it can increase the height of the stack by at most one symbol.That is for any rule $\delta(q,a,Z)$ contains $(p,\gamma),$ it must be that $|\gamma|\leq 2.$ Show that if $P$ is a $PDA,$then there is a restricted $PDA$ $P_{3},$such that $L(P)=L(P_{3}).$
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
admin asked Apr 6, 2019
162 views
Ullman (TOC) Edition 3 Exercise 6.2 Question 7 (Page No. 242)
How that if $P$ is a $PDA,$ then there is a $PDA$ $P_{2}$ with only two stack symbols such that $L(P_{2}=L(P).$ Hint$:$ Binary-code the stack alphabet of $P$
How that if $P$ is a $PDA,$ then there is a $PDA$ $P_{2}$ with only two stack symbols such that $L(P_{2}=L(P).$ Hint$:$ Binary-code the stack alphabet of $P$
User Avatar
0 votes
0 votes
0 answers
4
admin asked Apr 6, 2019
197 views
Ullman (TOC) Edition 3 Exercise 6.2 Question 4 (Page No. 242)
Let P be a PDA with empty-stack language $L=N(P),$ and suppose that $\in$ is not in $L.$Describe how you would modify $P,$ so that it accepts $L\cup \{\in\} $ by empty stack.
Let P be a PDA with empty-stack language $L=N(P),$ and suppose that $\in$ is not in $L.$Describe how you would modify $P,$ so that it accepts $L\cup \{\in\} $ by empty st...
User Avatar
Link Copied!