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 9.5 Question 2 (Page No. 418)
Show that the language $\overline{L_A}\cup \overline{L_B}$ is a regular language if and only if it is the set of all strings over its alphabet;i.e., if and only if the instance $(A,B)$ of PCP has no ... homomorphism, complementation and the pumping lemma for regular sets to show that $\overline{L_A}\cup \overline{L_B}$ is not regular.
asked
Jul 26
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

34
views
ullman
theoryofcomputation
regularlanguages
pcp
descriptive
0
votes
0
answers
2
Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) contextfree grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.
asked
Jul 26
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

9
views
ullman
theoryofcomputation
contextfreegrammars
pcp
descriptive
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 9.4 Question 4 (Page No. 412)
A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\Sigma$, we say that $wy\vdash yx$. That is ... . If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

64
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 9.4 Question 3 (Page No. 412)
Suppose we limited $PCP$ to a onesymbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

14
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
5
Ullman (TOC) Edition 3 Exercise 9.4 Question 2 (Page No. 412)
We showed that $PCP$ was undecidable, but we assumed that the alphabet $\Sigma$ could be arbitrary. Show that $PCP$ is undecidable even if we limit the alphabet to $\Sigma = \left\{0,1\right\}$ by reducing $PCP$ to this special case of $PCP$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

10
views
ullman
theoryofcomputation
undecidable
postcorrespondenceproblem
descriptive
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 9.4 Question 1 (Page No. 412)
Tell whether each of the following instances of $PCP$ has a solution. Each is presented as two lists $A$ and $B$, and the $i^{th}$ strings on the two lists correspond for each $i = 1,2,\cdot\cdot\cdot\cdot$ $A=(01,001,10); \ B = (011,10,00).$ $A=(01,001,10); \ B = (011,01,00).$ $A=(ab,a,bc,c); \ B = (bc,ab,ca,a).$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

13
views
ullman
theoryofcomputation
postcorrespondenceproblem
descriptive
0
votes
0
answers
7
Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)
Tell whether each of the following are recursive, REbutnotrecursive, or nonRE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM's$ ... that halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

18
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400  401)
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$. ... $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

12
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
9
Ullman (TOC) Edition 3 Exercise 9.3 Question 6 (Page No. 400)
Show that the following questions are decidable: The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its tape. Hint: If $M$ has $m$ states, consider the first $m$ transitions ... $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

18
views
ullman
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
0
answers
10
Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

11
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
11
Ullman (TOC) Edition 3 Exercise 9.3 Question 4 (Page No. 400)
We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or nonRE? Does $L(M)$ contain at least two strings? Is $L(M)$ infinite? Is $L(M)$ a contextfree language? Is $L(M) = (L(M))^{R}$?
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

9
views
ullman
theoryofcomputation
ricetheorem
descriptive
0
votes
0
answers
12
Ullman (TOC) Edition 3 Exercise 9.3 Question 3 (Page No. 400)
Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

5
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
0
votes
0
answers
13
Ullman (TOC) Edition 3 Exercise 9.3 Question 2 (Page No. 400)
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a hightech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary ... that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
14
Ullman (TOC) Edition 3 Exercise 9.3 Question 1 (Page No. 400)
Show that the set of Turingmachine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

20
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
0
votes
0
answers
15
Ullman (TOC) Edition 3 Exercise 9.2 Question 6 (Page No. 392)
We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the recursive languages and/or the RE ... , constructions to show closure. Union. Intersection. Concatenation. Kleene closure(star). Homomorphism. Inverse homomorphism.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
16
Ullman (TOC) Edition 3 Exercise 9.2 Question 5 (Page No. 392)
Let $L$ be recursively enumerable and let $\overline{L}$ be nonRE. Consider the language $L' = \left\{0w\mid w\ \text{is in}\ L \right\}$ Can you say for certain whether $L'$ or its complement are recursive, RE, or nonRE? Justify your answer.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

8
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
17
Ullman (TOC) Edition 3 Exercise 9.2 Question 4 (Page No. 391)
Let $L_{1},L_{2},\cdot\cdot\cdot,L_{k}$ be a collection of languages over alphbet $\Sigma$ such that: For all $i\neq j$, $L_{i}\cap L_{j}=\phi$ ... languages $L_{i}$, for $i=1,2,\cdot\cdot\cdot,k$ is recursively enumerable. Prove that each of the languages is therefore recursive.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

10
views
ullman
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
18
Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 9.2 Question 2 (Page No. 390  391)
In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore an ... following: Evaluate $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
ackermannsfunction
descriptive
0
votes
0
answers
20
Ullman (TOC) Edition 3 Exercise 9.2 Question 1 (Page No. 390)
Show that the halting problem, the set of $(M,w)$ pairs such that $M$ halts (with or without accepting) when given input $w$ is $RE$ but not recursive.$ ($See the box on "The Halting Problem" in Section $9.2.4)$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
haltingproblem
0
votes
0
answers
21
Ullman (TOC) Edition 3 Exercise 9.1 Question 4 (Page No. 383)
We have considered only Turing machines that have input alphabet $\left\{0,1\right\}$. Suppose that we wanted to assign an integer to all Turing machines, regardless of their input alphabet. That is not quite possible because while ... could assign an integer to all $TM's$ that had a finite subset of these symbols as its input alphabet.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
22
Ullman (TOC) Edition 3 Exercise 9.1 Question 3 (Page No. 382)
Here are two definitions of languages that are similar to the definition of $L_{d}$, yet different from that language. For each, show that the language is not accepted by a Turing machine, using a diagonalizationtype argument. Note that you cannot develop ... $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

5
views
ullman
theoryofcomputation
turingmachine
diagonalization
descriptive
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 9.1 Question 2 (Page No. 382)
Write one of the possible codes for the Turing machine of Fig.$8.9.$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

2
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 9.1 Question 1 (Page No. 382)
What strings are: $w_{37}$? $w_{100}$?
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
srtings
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 8.5 Question 2 (Page No. 362)
The purpose of this exercise is to show that a onestack machine with an endmarker on the input has no more power than a deterministic $PDA$. $L\$ is the concatenation of language $L$ with the language containing only the one string $\$ ... $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
dpda
descriptive
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 8.5 Question 1 (Page No. 361)
Informally but clearly describe counter machines that accept the following languages. In each case, use as few counters as possible,but not more than two counters. $\left\{0^{n}1^{m} \mid n\geq m\geq 1\right\}.$ ... $\left\{a^{i}b^{j}c^{k} \mid i=j \ \text{or} \ i=k \ \text{or}\ j=k\right\}.$
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

5
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 8.4 Question 10 (Page No. 352)
A twodimensional Turing machine has the usual finitestate control but a tape that is a twodimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the ... Prove that the languages accepted by twodimensional Turing machines are the same as those accepted by ordinary $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 8.4 Question 9 (Page No. 352)
A $k$head Turing machine has $k$ heads reading cells of one tape. A move of this $TM$ depends on the state and on the symbol scanned by each head. In one move, the $TM$ can change state, write a new symbol on ... there. Prove that the languages accepted by $k$head Turing machines are the same as those accepted by ordinary $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 8.4 Question 8 (Page No. 351  352)
In Fig. $8.17$ we saw an example of the general simulation of a $k$tape $TM$ by a onetape $TM.$ Suppose this technique is used to simulate a $5$tape $TM$ that had a tape alphabet of seven symbols. ... reduce the number of tape symbols of the onetape $TM$? Does it have any drawbacks compared with the other methods discussed?
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

5
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 8.4 Question 7 (Page No. 351)
In this exercise, we shall implement a stack using a special $3$tape $TM$. The first tape will be used only to hold and read the input. The input alphabet consists of the symbol $\uparrow$ , which we shall interpret as ... transition function of the $TM$ informally but clearly. Also, give a summary of the purpose of each state you use.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged ullman
Recent Blog Comments
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
@Ayush Upadhyaya Thank you so much! ^_^
50,645
questions
56,596
answers
195,823
comments
102,068
users