search
Log In

Recent questions tagged ullman

0 votes
0 answers
1
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 solution. Thus, prove that it is ... closed under inverse 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, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
0 votes
0 answers
2
Let $L$ be the set of (codes for) context-free 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, 2019 in Theory of Computation Lakshman Patel RJIT 25 views
0 votes
0 answers
3
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$ ... by one move of $M$. If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 89 views
0 votes
0 answers
5
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, 2019 in Theory of Computation Lakshman Patel RJIT 20 views
0 votes
0 answers
6
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, 2019 in Theory of Computation Lakshman Patel RJIT 24 views
0 votes
0 answers
7
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE. 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 no 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, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
0 votes
0 answers
8
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$. The set of triples $(M_{1},M_{2},M_{3})$ such that $L(M_{1}) = L(M_{2})L(M_{3})$ ; i.e., the language of the first is the concatenation of the languages of the two $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
9
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$ ... . The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 31 views
0 votes
1 answer
11
We know by Rice's theorem that none of the following problems are decidable. However are they recursively enumerable,or non-RE? Does $L(M)$ contain at least two strings? Is $L(M)$ infinite? Is $L(M)$ a context-free language? Is $L(M) = (L(M))^{R}$?
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
0 votes
0 answers
12
0 votes
0 answers
13
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary Turing machine, except that each state of ... just entered. Prove that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 36 views
0 votes
0 answers
14
0 votes
0 answers
15
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 languages are closed under the following ... informal, but clear, constructions to show closure. Union. Intersection. Concatenation. Kleene closure(star). Homomorphism. Inverse homomorphism.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 24 views
0 votes
0 answers
16
0 votes
0 answers
17
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$ ... the languages. Each of the 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, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
18
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$ ... be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
19
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 example of the recursive-function notation. A recursive function is a ... $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 61 views
0 votes
0 answers
20
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, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
21
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 the names of the states or noninput tape ... chosen. Show how we could assign an integer to all $TM's$ that had a finite subset of these symbols as its input alphabet.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
0 votes
0 answers
22
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 diagonalization-type argument. Note that you cannot develop an argument based on the diagonal itself, ... not accepted by $M_{2i}$. The set of all $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 48 views
0 votes
0 answers
25
The purpose of this exercise is to show that a one-stack 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 $\$; that is, $L\$ is the set of all strings $w\$ such ... is the set of states $q$ such that $P$,started in $ID\ (q,a,X_{i}X_{i+1}\cdot \cdot X_{n})$ will accept.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
26
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\{0^{n}1^{m} \mid m\geq n\geq 1\right\}.$ $\left\{a^{i}b^{j}c^{k} \mid i=j \text{or} i=k\right\}.$ $\left\{a^{i}b^{j}c^{k} \mid i=j \ \text{or} \ i=k \ \text{or}\ j=k\right\}.$
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
27
A two-dimensional Turing machine has the usual finite-state control but a tape that is a two-dimensional grid of cells, infinite in all directions. The input is placed on one row of the grid, with the head at the left end of the input and the control in ... state, also as usual. Prove that the languages accepted by two-dimensional Turing machines are the same as those accepted by ordinary $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 19 views
0 votes
0 answers
28
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 the cell scanned by each head, and ... one that actually gets written there. Prove that the languages accepted by $k$-head Turing machines are the same as those accepted by ordinary $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
29
In Fig. $8.17$ we saw an example of the general simulation of a $k$-tape $TM$ by a one-tape $TM.$ Suppose this technique is used to simulate a $5$-tape $TM$ that had a tape alphabet of seven symbols. How many tape symbols would the one-tape $TM$ ... $TM$? Does it have any drawbacks compared with the other methods discussed?
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 13 views
0 votes
0 answers
30
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 "pop the stack," and the symbols $a$ ... $q_{f}$. Describe the transition function of the $TM$ informally but clearly. Also, give a summary of the purpose of each state you use.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
...