The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged ullman
0
votes
0
answers
1
Ullman (TOC) Edition 3 Exercise 8.4 Question 6 (Page No. 351)
Design the following $2$tape $TM$ to accept the language of all strings of $0's$ and $1's$ with an equal number of each. The first tape contains the input, and is scanned from left to right. The second tape is ...  versa, in the part of the input seen so far. Specify the states, transitions, and the intuitive purpose of each state.
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

8
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 8.4 Question 5 (Page No. 350)
Consider a nondeterministic $TM$ whose tape is infinite in both directions. At some time, the tape is completely blank, except for one cell, which holds the symbol $\$ ... Suppose the $TM$ were deterministic instead. How would you enable it to find the $\$ and enter state $p?$
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

6
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 8.4 Question 4 (Page No. 350)
Consider the nondeterministic Turing machine $M=\left(\left\{q_{0},q_{1},q_{2},q_{f}\right\},\left\{0,1 \right\},\left\{0,1,B \right\} ,\delta,q_{0},B,q_{f}\right)$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the ...
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

4
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 8.4 Question 3 (Page No. 350)
Informally but clearly describe nondeterministic Turing machines $$ multitape if you like $$ that accept the following languages. Try to take advantage of nondeterminism to avoid iteration and save time in the non  deterministic sense. That is, prefer to ... but for at least two values of $j$, we have $w_{j}$ equal to $j$ in binary.
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

8
views
ullman
theoryofcomputation
turingmachine
ntm
descriptive
0
votes
0
answers
5
Ullman (TOC) Edition 3 Exercise 8.4 Question 2 (Page No. 350)
Here is the transition function of a nondeterministic $TM \ \ M = \left(\left\{ q_{0},q_{1},q_{2}\right\},\left\{0,1\right\},\left\{0,1,B\right\},\delta,q_{0},B,\left\{q_{2}\right\} \right):$ Show the $ID's$ reachable from the initial $ID$ if the input is: $01$ $011$
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

9
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 8.4 Question 1 (Page No. 349)
Informally but clearly describe multitape Turing machines that accept each of the languages of The set of strings with an equal number of $0's$ and $1's.$ $\left\{a^{n}b^{n}c^{n}\ \mid n\geq 1\right\}.$ ... Try to make each of your Turing machines run in time proportional to the input length.
asked
Jul 20
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

15
views
ullman
theoryofcomputation
multitapeturingmachine
descriptive
0
votes
0
answers
7
Compiler Design: Self Doubt on Operator Grammar
Say I have a grammar, S→ AB A→ a B→ b This grammar is not operator grammar as 2 non terminals are lying side by side, but can be converted to an operator grammar. S→ ab , A→ a , B→ b here i have a doubt, operator grammar ... can we operate even two terminal symbols when placed side by side? Isn't it same as placing 2 nonterminal symbol side by side?
asked
Jun 6
in
Compiler Design
by
Hirak
Active
(
3.5k
points)

44
views
compilerdesign
operatorgrammar
ullman
0
votes
0
answers
8
Molina Exercise6.3.1 Question nof Page no280 SQL
Product(maker, model, type) PC(model, speed, ram, hd, price) Laptop(model, speed, ram, hd, screen, price) Printer(model, color, type, price) Find the maker(s) of the PC(s) with the fastest processor among all those PC 's that have the ... p where p.speed IN( select max(p1.speed) from PC p1 where p1.ram IN( select MIN(p2.ram) from PC p2)))
asked
May 8
in
Databases
by
aditi19
Active
(
5.1k
points)

40
views
ullman
databases
sql
query
0
votes
1
answer
9
Molina Exercise6.2.2 page267 SQL
Product(maker, model, type) PC(model, speed, ram, hd, price) Laptop(model, speed, ram, hd, screen, price) Find those manufacturers of at least two different computers (PC's or laptops) with speeds of at least 3.0 is my query ... AND count(distinct model)>=2 UNION select maker from Product NATURAL JOIN Laptop where speed>=3 AND count(distinct model)>=2
asked
May 7
in
Databases
by
aditi19
Active
(
5.1k
points)

54
views
databases
sql
naturaljoin
joins
ullman
0
votes
0
answers
10
Ullman (Compiler Design) Edition 2 Exercise 1.1 Question 5 (Page No. 3)
Describe some of the tasks that an assembler needs to perform.
asked
Apr 15
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

38
views
ullman
compilerdesign
introduction
descriptive
0
votes
0
answers
11
Ullman (Compiler Design) Edition 2 Exercise 1.1 Question 4 (Page No. 3)
A compiler that translates a highlevel language into another highlevel language is called a sourcetosource translator. What advantages are there to using C as a target language for a compiler?
asked
Apr 15
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

24
views
ullman
compilerdesign
introduction
0
votes
0
answers
12
Ullman (Compiler Design) Edition 2 Exercise 1.1 Question 3 (Page No. 3)
What advantages are there to a language processing system in which the compiler produces assembly language rather than machine language?
asked
Apr 15
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

23
views
ullman
compilerdesign
introduction
0
votes
0
answers
13
Ullman (Compiler Design) Edition 2 Exercise 1.1 Question 2 (Page No. 3)
What are the advantages of a compiler over an interpreter? an interpreter over a compiler?
asked
Apr 15
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

21
views
ullman
compilerdesign
introduction
0
votes
0
answers
14
Ullman (Compiler Design) Edition 2 Exercise 1.1 Question 1 (Page No. 3)
What is the difference between a compiler and an interpreter$?$
asked
Apr 15
in
Compiler Design
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

20
views
ullman
compilerdesign
introduction
0
votes
0
answers
15
Ullman (TOC) Edition 3 Exercise 8.3 Question 3 (Page No. 343)
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not hold $0,$ then the TM should halt. You may assume that there are no tape ... a TM that accepts all strings of $0's$ and $1's$ that do not have two $1's$ in a row$.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

34
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
16
Ullman (TOC) Edition 3 Exercise 8.3 Question 2 (Page No. 343)
A common operation in Turingmachine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit ... perform this operation. Hint $:$ Leave a special symbol to mark the position to which the head must return.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

26
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
17
Ullman (TOC) Edition 3 Exercise 8.3 Question 1 (Page No. 343)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$ Redesign your Turing machines from Exercise $8.2$ to take advantage of the programming techniques.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
18
Ullman (TOC) Edition 3 Exercise 8.2 Question 5 (Page No. 337)
Consider the Turing machine $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules$:$ ...
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 8.2 Question 4 (Page No. 336)
In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem ... $?$ If not, explain how you could modify the construction to make it work.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

34
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
20
Ullman (TOC) Edition 3 Exercise 8.2 Question 3 (Page No. 336)
Design a Turing machine that takes as input a number $N$ and adds $1$ to it in binary. To be precise, the tape initially contains a $ \$ $ followed by $N$ in binary. The tape head is initially scanning the $ \$ $ in state ... $ of your TM when given input $\$111.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

32
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
21
Ullman (TOC) Edition 3 Exercise 8.2 Question 2 (Page No. 335  336)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

20
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
22
Ullman (TOC) Edition 3 Exercise 8.2 Question 1 (Page No. 335)
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$ $00$ $000111$ $00111$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 8.1 Question 1 (Page No. 324)
Give reductions from the helloworld problem to each of the problems below. Use the informal style of this section for describing plausible program transformations, and do not worry about the real limits such as maximum file size or ... $?$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

18
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 7.4 Question 5 (Page No. 308)
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

24
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 7.4 Question 4 (Page No. 308)
Show that in any $CNF$ grammar all parse trees for strings of length $n$ have $2n1$ interior nodes $(i.e.,$ $2n1$ nodes with variables for lables$).$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

22
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 7.4 Question 3 (Page No. 308)
Using the grammar $G$ of Example $7.34,$use the $CYK$ algorithm to determine whether each of the following strings is in $L(G):$ $ababa$ $baaab$ $aabab$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

27
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 7.4 Question 2 (Page No. 308)
Use the technique described in Section $7.4.3$ to develop linear time algorithms for the following questions about $CFG's:$ Which symbols appear in some sentential form$?$ Which symbols are nullable $\text{(derive $\in$)?}$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

8
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 7.4 Question 1 (Page No. 307  308)
Give algorithms to decide the following$:$ Is $L(G)$ fi nite, for a given CFG $G?$ Hint$:$ Use the pumping lemma. Does $L(G)$ contain at least $100$ strings, for a given CFG $G?$ Given a CFG $G$ and one of ... for $A$ to appear first in the middle of some sentential form but then for all the symbols to its left to derive $\in.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

4
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 7.3 Question 7 (Page No. 299)
Complete the proof of theorem $7.27$ by showing that $(q_{P},w,Z_{0})\vdash(q,\in,\gamma)$ if and only if $(q_{P},q_{A},w,Z_{0}) \vdash((q,p),\in,\gamma),$ where $p =\hat{\delta}(p_{A},w).$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

11
views
ullman
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 7.3 Question 6 (Page No. 298)
Give the formal proof of theorem $7.25:$ that the $CFL's$ are closed under reversal.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.8k
points)

19
views
ullman
theoryofcomputation
contextfreelanguages
proof
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
next »
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged ullman
Recent Blog Comments
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
i also don't have any pdf, actually, I added the...
50,646
questions
56,505
answers
195,541
comments
100,978
users