Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
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).$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
248
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
212
Ullman (TOC) Edition 3 Exercise 6.3 Question 5 (Page No. 252)
Below are some context-free languages.For each,devise a PDA that accepts the language by empty stack. You may ,if you wish, first construct a grammar for the language, and then convert to a $PDA:$ $\{a^{n}b^{m}c^{2(n+m)}|n\geq 0,m\geq 0\}$ $\{a^{i}b^{j}c^{k}|i=2j $(or)$ j=2k\}$ $\{0^{n}1^{m}|n\leq m\leq 2n\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
279
views
ullman
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
0
answers
213
Ullman (TOC) Edition 3 Exercise 6.3 Question 4 (Page No. 252)
Convert the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ to a $CFG,$ if $\delta$ given by $:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ $\delta(q,\in,X)=\{p,\in\}$ $\delta(p,\in,X)=\{p,\in\}$ $\delta(p,1,X)=\{(p,XX)\}$ $\delta(p,1,Z_{0})=\{p,\in\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
183
views
ullman
theory-of-computation
pushdown-automata
context-free-grammar
0
votes
0
answers
214
Ullman (TOC) Edition 3 Exercise 6.3 Question 3 (Page No. 251)
Convert the $PDA$ $P=(\{p,q\},\{0,1\},\{X,Z_{0}\},\delta.q.Z_{0})$ to a $CFG,$ if $\delta$ is given by $:$ $\delta(q,1,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,1,X)=\{(q,XX)\}$ $\delta(q,0,X)=\{(p,X)\}$ $\delta(q,\in,X)=\{(q,\in)\}$ $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
149
views
ullman
pushdown-automata
context-free-grammar
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.
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
204
views
ullman
theory-of-computation
pushdown-automata
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.
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
264
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
217
Ullman (TOC) Edition 3 Exercise 6.2 Question 8 (Page No. 242)
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}).$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
552
views
ullman
theory-of-computation
pushdown-automata
descriptive
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$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
164
views
ullman
theory-of-computation
pushdown-automata
descriptive
1
vote
0
answers
219
Ullman (TOC) Edition 3 Exercise 6.2 Question 6 (Page No. 242)
Suppose th $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ ... $PDA$ $P_{2}$ such that $L(P_{2})=N(P)$ i.e., $P_{2}$ accepts by final state what $P$ accepts by empty stack.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
223
views
ullman
theory-of-computation
pushdown-automata
descriptive
1
vote
0
answers
220
Ullman (TOC) Edition 3 Exercise 6.2 Question 5 (Page No. 242)
$PDA$ $P=(\{q_{0},q_{1},q_{2},q_{3},f)\},\{a,b\},\{Z_{0},A,B\},\delta,q_{0},Z_{0},\{f\})$ has the following rules defining $\delta:$ $\delta(q_{0},a,Z_{0})=(q_{1},AAZ_{0})$ ... that $abb$ is in $L(P)$ Give the contents of the stack after $P$ have read $b^{7}a^{4}$ from its input. Informally describe $L(P)?$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
479
views
ullman
theory-of-computation
pushdown-automata
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.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
190
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
222
Ullman (TOC) Edition 3 Exercise 6.2 Question 3 (Page No. 242)
Design a PDA to accept each of the following languages. $\{a^{i}b^{j}c^{k}| i \neq j$ $(or) j\neq k\}.$ The set of all strings of $a's$ and $b's$ that are not on the form $ww,$that is, not equal to any string repeated.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
220
views
ullman
theory-of-computation
pushdown-automata
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.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
215
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
224
Ullman (TOC) Edition 3 Exercise 6.2 Question 1 (Page No. 241)
Design a PDA to accept each of the following languages. You may accept either by final state or by empty stack, whichever is more convenient. $\{0^{n}1^{n}|n\geq 1\}$ The set of all strings of $0's$ and $1's$ such that ... $0's$ and $1's$ with an equal number of $0's$ and $1's.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
631
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
225
Ullman (TOC) Edition 3 Exercise 6.1 Question 1 (Page No. 233 - 234)
Suppose the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ ... $ID$ $(q,w,Z_{0}),$show all the reachable $ID's$ when the input $w$ is $:$ $01$ $0011$ $010$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
285
views
ullman
theory-of-computation
pushdown-automata
0
votes
0
answers
226
Ullman (TOC) Edition 3 Exercise 5.4 Question 7 (Page No. 216)
Suppose th PDA $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ ... $ID$ $(q,w,Z_{0}),$show all the reachable $ID's$ when the input $w$ is $:$ $01$ $0011$ $010$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
145
views
ullman
theory-of-computation
pus
4
votes
0
answers
227
Ullman (TOC) Edition 3 Exercise 5.4 Question 7 (Page No. 216)
The following grammar generates prefix expressions with operands $x$ and $y$ and binary operators $+,-$ and $*$ $:$ $E\rightarrow +EE|*EE|-EE|x|y$ Find leftmost and rightmost derivations and a derivation tree for the string $+*-xyxy.$ Prove that this grammar is unambiguous.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
749
views
ullman
theory-of-computation
context-free-grammar
context-free-language
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.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
282
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
229
Ullman (TOC) Edition 3 Exercise 5.4 Question 5 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Show that this grammar is unambiguous. Find a grammar for the same language that is ambiguous and demonstrate its ambiguity.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
199
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
230
Ullman (TOC) Edition 3 Exercise 5.4 Question 4 (Page No. 216)
Some strings of $a's$ and $b's$ have a unique parse tree in the grammar of $S\rightarrow aS|aSbS|\in.$ Give an efficient test to tell whether a given string is one of these. The test $"$try all parse trees to see how many yield the given string$"$ is not adequately efficient$.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
220
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
231
Ullman (TOC) Edition 3 Exercise 5.4 Question 3 (Page No. 216)
Find an unambiguous grammar for the language of $S\rightarrow aS|aSbS|\in$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
205
views
ullman
theory-of-computation
context-free-grammar
context-free-language
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$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
183
views
ullman
theory-of-computation
context-free-grammar
context-free-language
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
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
145
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
234
Ullman (TOC) Edition 3 Exercise 5.2 Question 4 (Page No. 193)
If $X_{1}X_{2}.....X_{k}\overset{*}\Rightarrow \alpha,$ then all the positions of $\alpha$ that come from expansion of $X_{i}$ are to the left of all the positions that come from expansion of $X_{j},$ if $i<j.$ Prove this fact$.$ Hint$:$ Perform an induction on the number of steps in the derivation$.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
151
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
235
Ullman (TOC) Edition 3 Exercise 5.2 Question 3 (Page No. 193)
Suppose all is as in question $2,$ but $G$ may have some productions with $\in$ as the right side. Show that a parse tree for a string $w$ other than $\in$ may have as many as $n+2m-1$ nodes,but no more.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
340
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
236
Ullman (TOC) Edition 3 Exercise 5.2 Question 2 (Page No. 193)
Suppose that $G$ is a $CFG$ without any productions that have $\in$ as the right side. If $w$ is in $L(G),$ the length of $w$ is $n$ and $w$ has a derivation of $m$ steps, show that $w$ has a parse tree with $n+m$ nodes.
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
182
views
ullman
theory-of-computation
context-free-grammar
context-free-language
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$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
110
views
ullman
theory-of-computation
context-free-grammar
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.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
1.3k
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
1
answer
239
Ullman (TOC) Edition 3 Exercise 5.1 Question 7 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$ $S\rightarrow aS|Sb|a|b$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. Describe $L(G)$ informally. Justify your answer using part $(a).$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
1.8k
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
240
Ullman (TOC) Edition 3 Exercise 5.1 Question 6 (Page No. 182 - 183)
We defined the relation $\overset{*}\Rightarrow$ with a basis $"\alpha\Rightarrow \alpha $ and an induction that says $\alpha\overset{*}\Rightarrow\beta$ and $\beta\Rightarrow\gamma$ ... $:$ Use induction on the number of steps in the derivation $\beta\overset{*}\Rightarrow\gamma.$
admin
asked
in
Theory of Computation
Apr 6, 2019
by
admin
214
views
ullman
theory-of-computation
context-free-grammar
context-free-language
Page:
« prev
1
...
3
4
5
6
7
8
9
10
11
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged ullman
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...