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
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged ullman
0
votes
0
answers
1
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.1k
points)

24
views
compilerdesign
operatorgrammar
ullman
0
votes
0
answers
2
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
(
3.7k
points)

18
views
ullman
databases
sql
query
0
votes
1
answer
3
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
(
3.7k
points)

27
views
databases
sql
naturaljoin
joins
ullman
0
votes
0
answers
4
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
Boss
(
40k
points)

35
views
ullman
compilerdesign
introduction
0
votes
0
answers
5
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
Boss
(
40k
points)

21
views
ullman
compilerdesign
introduction
0
votes
0
answers
6
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
Boss
(
40k
points)

21
views
ullman
compilerdesign
introduction
0
votes
0
answers
7
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
Boss
(
40k
points)

19
views
ullman
compilerdesign
introduction
0
votes
0
answers
8
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
Boss
(
40k
points)

14
views
ullman
compilerdesign
introduction
0
votes
0
answers
9
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
Boss
(
40k
points)

31
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
10
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
Boss
(
40k
points)

24
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
11
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
Boss
(
40k
points)

24
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
12
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
Boss
(
40k
points)

23
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
13
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
Boss
(
40k
points)

32
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
14
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
Boss
(
40k
points)

29
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
15
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
Boss
(
40k
points)

17
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
16
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
Boss
(
40k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
17
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
Boss
(
40k
points)

14
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
18
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
Boss
(
40k
points)

22
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
19
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
Boss
(
40k
points)

19
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
20
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
Boss
(
40k
points)

22
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
21
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
Boss
(
40k
points)

6
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
22
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
Boss
(
40k
points)

4
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
23
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
Boss
(
40k
points)

8
views
ullman
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
24
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
Boss
(
40k
points)

16
views
ullman
theoryofcomputation
contextfreelanguages
proof
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 7.3 Question 5 (Page No. 298)
A string $y$ is said to be a permutation of the string $x$ if the symbols of $y$ can be reordered to make $x.$ For instance, the permutations of string $x=011$ are $110,101,$ and $011.$ If $L$ is a language then ... not contextfree. Prove that for every regular language $L$ over a twosymbol alphabet , $\text{perm(L)}$ is contextfree.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

16
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 7.3 Question 4 (Page No. 297  298)
The $\text{shuffle}$ of two strings $w$ and $x$ is the set of all strings that one can get by interleaving the positions of $w$ and $x$ in any way. More precisely $,\text{shuffle(w,x)}$ is the set of strings $z$ such that Each position of ... $L_{2}$ are both $CFL's,$ then $\text{shuffle($L_{1},L_{2}$)}$ need not be a $CFL.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

11
views
ullman
theoryofcomputation
contextfreelanguages
descriptive
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 7.3 Question 3 (Page No. 297)
Show that the $CFL's$ are not closed under the following operations$:$ $\text{min}$ $\text{max}$ $\text{half}$ $\text{alt}$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

5
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 7.3 Question 2 (Page No. 297)
Consider the following languages$:$ $L_{1}=\{a^{n}b^{2n}c^{m}n,m\geq 0\}$ $L_{2}=\{a^{n}b^{m}c^{2m}n,m\geq 0\}$ Show that each of these languages is contextfree by giving grammars for each. Is $L_{1}\cap L_{2}$ a $CFL?$ Justify your answer.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

8
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 7.3 Question 1 (Page No. 297)
Show that the $CFL's$ are closed under the following$:$ $\text{init},$ Hint$:$ Start with a $CNF$ grammar for the language $L.$ $\text{The operation $L/a,$}$ Hint$:$ Again,start with a $CNF$ grammar for $L.$ $\text{cycle, }$ Hint$:$ Try a $PDA$based constrction.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

4
views
ullman
theoryofcomputation
contextfreelanguages
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 7.2 Question 5 (Page No. 287)
Use Ogden's lemma $($Question $3)$ to show that the following languages are not $CFL's:$ $\{0^{i}1^{j}0^{k}k=max(i,k)\}.$ $\{a^{n}b^{n}c^{i}i\neq n\}.$ Hint$:$ If $n$ is the constant for Ogden's lemma,consider the stirng $z=a^{n}b^{n}c^{n+n!}.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
40k
points)

4
views
ullman
theoryofcomputation
contextfreelanguages
Page:
1
2
3
4
5
6
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
Success From Failure  IIITH Interview Experience
IIITH Preparation and interview experience (M.Tech CSE)
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Follow @csegate
Recent questions tagged ullman
Recent Blog Comments
Please suggest links where I can find exercise...
Yes
@
49,587
questions
54,197
answers
187,535
comments
71,151
users