Register

Recent questions tagged ullman

0 votes
0 answers
211
Ullman (TOC) Edition 3 Exercise 6.3 Question 6 (Page No. 252)
Show that if $P$ is a PDA, then there is a one-state PDA $,P_{1},$ such that $N(P_{1})=N(P).$
Show that if $P$ is a PDA, then there is a one-state PDA $,P_{1},$ such that $N(P_{1})=N(P).$
User Avatar
0 votes
0 answers
215
Ullman (TOC) Edition 3 Exercise 6.3 Question 2 (Page No. 251)
Convert the grammar $S\rightarrow aAA$ $A\rightarrow aS|bS|a$ to a PDA that accepts the same language by empty stack.
Convert the grammar $S\rightarrow aAA$ $A\rightarrow aS|bS|a$to a PDA that accepts the same language by empty stack.
User Avatar
0 votes
0 answers
216
Ullman (TOC) Edition 3 Exercise 6.3 Question 1 (Page No. 251)
Convert the grammar $S\rightarrow 0S1|A$ $A\rightarrow 1A0|S|\in$ to a PDA that accepts the same language by empty stack.
Convert the grammar $S\rightarrow 0S1|A$ $A\rightarrow 1A0|S|\in$to a PDA that accepts the same language by empty stack.
User Avatar
0 votes
0 answers
218
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 answers
221
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
0 votes
0 answers
223
Ullman (TOC) Edition 3 Exercise 6.2 Question 2 (Page No. 241 - 242)
Design a PDA to accept each of the following languages. $\{a^{i}b^{j}c^{k}| i = j $ $(or)$ $j = k\}.$ The set of all strings with twice as many $0's$ as $1's.$
Design a PDA to accept each of the following languages.$\{a^{i}b^{j}c^{k}| i = j $ $(or)$ $j = k\}.$The set of all strings with twice as many $0's$ as $1's.$
User Avatar
0 votes
0 answers
228
Ullman (TOC) Edition 3 Exercise 5.4 Question 6 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Is your grammar is unambiguous$?$ If not,redesign it to be unambiguous.
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Is your grammar is unambiguous$?$ If not,redesign it to be unambi...
User Avatar
0 votes
0 answers
232
Ullman (TOC) Edition 3 Exercise 5.4 Question 2 (Page No. 216)
Prove that the grammar generates all only the strings of $a's$ and $b's$ such that every prefix has at least as many $a's$ as $b's.$ $S\rightarrow aS|aSbS|\in$
Prove that the grammar generates all only the strings of $a's$ and $b's$ such that every prefix has at least as many $a's$ as $b's.$ $S\rightarrow aS|aSbS|\in...
User Avatar
0 votes
0 answers
233
Ullman (TOC) Edition 3 Exercise 5.4 Question 1 (Page No. 215)
Consider the grammar $S\rightarrow aS|aSbS|\in$ This grammar is ambiguous. Show in particular that the string $aab$ has two$:$ Parse trees Leftmost derivations Rightmost derivations
Consider the grammar $S\rightarrow aS|aSbS|\in$This grammar is ambiguous. Show in particular that the string $aab$ has two$:$Parse treesLeftmost derivationsRightmost deri...
User Avatar
0 votes
0 answers
237
Ullman (TOC) Edition 3 Exercise 5.2 Question 1 (Page No. 193)
For the following grammar and each of the strings gives pase trees. $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow B|1B|\in$ $00101$ $1001$ $00011$
For the following grammar and each of the strings gives pase trees.$S\rightarrow A1B$$A\rightarrow 0A|\in$$B\rightarrow B|1B|\in$$00101$ $1001$ $00011$
User Avatar
0 votes
1 answer
238
Ullman (TOC) Edition 3 Exercise 5.1 Question 8 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aSbS|bSaS|\in$ Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
Consider the CFG $G$ defi ned by productions$:$$S\rightarrow aSbS|bSaS|\in$Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
User Avatar
Page: