Register

Recent questions tagged pushdown-automata

2 votes
0 answers
68
Ullman (TOC) Edition 3 Exercise 6.4 Question 2 (Page No. 256 - 257)
Give deterministic pushdown automata to accept the following languages$:$ $\{0^{n}1^{m}|n\leq m\}$ $\{0^{n}1^{m}|n\geq m\}$ $\text{\{$0^{n}1^{m}0^{n}$|n and m are arbitrary\}}$
Give deterministic pushdown automata to accept the following languages$:$$\{0^{n}1^{m}|n\leq m\}$$\{0^{n}1^{m}|n\geq m\}$$\text{\{$0^{n}1^{m}0^{n}$|n and m are arbitrary\...
User Avatar
0 votes
0 answers
71
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
75
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
76
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
1 answer
77
Vani institute question bank
5. For n ≥ 0, Ln = {a^i b^k | i ≥ n, 0 < k < i} (a) Ln is regular, independent of value of n (b) Ln is not regular, independent of value of n (c) Ln is regular only for small value of n (d) None of above
5. For n ≥ 0, Ln = {a^i b^k | i ≥ n, 0 < k < i} (a) Ln is regular, independent of value of n(b) Ln is not regular, independent of value of n(c) Ln is regular only ...
User Avatar
0 votes
0 answers
79
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
82
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
84
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
1 votes
1 answer
88
Cfg to and from pda
Do i have to study the conversation of pda to Cfg or cfg to pda? Is this an important concept with relevance to gate? I know how to individually make them though.
Do i have to study the conversation of pda to Cfg or cfg to pda? Is this an important concept with relevance to gate? I know how to individually make them though.
User Avatar
Page: