Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
0
votes
0
answers
1651
Peter Linz Edition 5 Exercise 12.3 Question 2 (Page No. 317)
$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be the process exhibited in Figure. Then the ... string $F$ as $v_1$. The order of the rest of the strings is immaterial. Provide the details of the proof of the Theorem.
$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be ...
Rishi yadav
153
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1652
Peter Linz Edition 5 Exercise 12.3 Question 1 (Page No. 317)
Let $A = \{001, 0011, 11, 101\}$ and $B = \{01, 111, 111, 010\}$. Does the pair $(A, B)$ have a PC solution$?$ Does it have an MPC solution$?$
Let $A = \{001, 0011, 11, 101\}$ and $B = \{01, 111, 111, 010\}$. Does the pair $(A, B)$ have a PC solution$?$ Does it have an MPC solution$?$
Rishi yadav
224
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1653
Self thought
We know that Regular languages are decidable under membership property and lets say $L$ is such a regular language. From Chomsky hierarchy we know that $\text{Regular languages}$ $\subset$ $\text{Recursively Enumerable Languages}$. Lets say there are two persons $A$ ... how can we conclude that $M$ will halt after processing $L$ or will not halt at all. Please explain with reason?
We know that Regular languages are decidable under membership property and lets say $L$ is such a regular language. From Chomsky hierarchy we know that $\text{Regular lan...
!KARAN
594
views
!KARAN
asked
Mar 16, 2019
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1654
Peter Linz Edition 5 Exercise 12.2 Question 8 (Page No. 311)
For an unrestricted grammar $G$, show that the question $“Is \space L(G) = L(G)^*?”$ is undecidable. Argue $\text(a)$ from Rice’s theorem and $\text(b)$ from first principles.
For an unrestricted grammar $G$, show that the question $“Is \space L(G) = L(G)^*?”$ is undecidable. Argue $\text(a)$ from Rice’s theorem and $\text(b)$ from first ...
Rishi yadav
193
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1655
Peter Linz Edition 5 Exercise 12.2 Question 7 (Page No. 311)
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\cap L(G_2) = \phi $ is undecidable for any fixed $G_2,$ as long as $L(G_2)$ is not empty.
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \spa...
Rishi yadav
173
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1656
Peter Linz Edition 5 Exercise 12.2 Question 6 (Page No. 311)
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\cap L(G_2) = \phi $ is undecidable.
Let $G_1$ be an unrestricted grammar, and $G_2$ any regular grammar. Show that the problem $L(G_1) \space\ca...
Rishi yadav
200
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1657
Peter Linz Edition 5 Exercise 12.2 Question 5 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G) = L(G)^R$$?$
Rishi yadav
759
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1658
Peter Linz Edition 5 Exercise 12.2 Question 4 (Page No. 311)
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
Let $G$ be an unrestricted grammar. Does there exist an algorithm for determining whether or not $L(G)^R$ is recursive enumerable$?$
Rishi yadav
295
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1659
Peter Linz Edition 5 Exercise 12.2 Question 3 (Page No. 311)
Let $M_1$ and $M_2$ be arbitrary Turing machines. Show that the problem $“L(M_1)\subseteq L(M_2)”$ is undecidable.
Let $M_1$ and $M_2$ be arbitrary Turing machines. Show that the problem $“L(M_1)\subseteq L(M_2)”$ is undecidable.
Rishi yadav
220
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1660
Peter Linz Edition 5 Exercise 12.2 Question 2 (Page No. 311)
Show that the two problems mentioned at the end of the preceding section, namely $\text(a)$ $L(M)$ contains any string of length five, $\text(b)$ $L(M)$ is regular, are undecidable.
Show that the two problems mentioned at the end of the preceding section, namely$\text(a)$ $L(M)$ contains any string of length five,$\text(b)$ $L(M)$ is regular,are unde...
Rishi yadav
210
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1661
Peter Linz Edition 5 Exercise 12.2 Question 1 (Page No. 311)
$\text{Theorem}:$ Let $M$ be any Turing machine. Then the question of whether or not $L(M)$ is finite is undecidable. Show in detail how the machine $\widehat{M}$ in $\text{Theorem}$ is constructed.
$\text{Theorem}:$ Let $M$ be any Turing machine. Then the question of whether or not $L(M)$ is finite is undecidable.Show in detail how the machine $\widehat{M}$ in $\tex...
Rishi yadav
171
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1662
Peter Linz Edition 5 Exercise 12.1 Question 16 (Page No. 308)
Determine whether or not the following statements is true: Any problem whose domain is finite is decidable.
Determine whether or not the following statements is true: Any problem whose domain is finite is decidable.
Rishi yadav
185
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1663
Peter Linz Edition 5 Exercise 12.1 Question 15 (Page No. 308)
Let $\Gamma = \{0,1,\square\}$ and let $b(n)$ be the maximum number of tape cells examined by any $n-$state Turing machine that halts when started with a blank tape. Show that $b(n)$ is not computable.
Let $\Gamma = \{0,1,\square\}$ and let $b(n)$ be the maximum number of tape cells examined by any $n-$state Turing machine that halts when started with a blank tape. Show...
Rishi yadav
138
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1664
Peter Linz Edition 5 Exercise 12.1 Question 14 (Page No. 308)
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines with this $\Gamma$.
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines wit...
Rishi yadav
147
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
1
votes
1
answer
1665
Peter Linz Edition 5 Exercise 12.1 Question 13 (Page No. 308)
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
Rishi yadav
351
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1666
Peter Linz Edition 5 Exercise 12.1 Question 12 (Page No. 308)
Show that the problem of determining whether a Turing machine halts on any input is undecidable.
Show that the problem of determining whether a Turing machine halts on any input is undecidable.
Rishi yadav
131
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1667
Peter Linz Edition 5 Exercise 12.1 Question 11 (Page No. 308)
Let $\Gamma = \{0,1,\square\}$. Consider the function $f(n)$ whose value is the maximum number of moves that can be made by any $n-state$ Turing machine that halts when started with a blank tape. This function, as it turns out, is not computable. Give the values of $f(1)$ and $f(2)$.
Let $\Gamma = \{0,1,\square\}$. Consider the function $f(n)$ whose value is the maximum number of moves that can be made by any $n-state$ Turing machine that halts when s...
Rishi yadav
139
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
+
–
0
votes
0
answers
1668
Peter Linz Edition 5 Exercise 12.1 Question 10 (Page No. 308)
Let $M$ be any Turing machine and $x$ and $y$ two possible instantaneous descriptions of it. Show that the problem of determining whether or not $x \vdash^{*}_M y$ is undecidable.
Let $M$ be any Turing machine and $x$ and $y$ two possible instantaneous descriptions of it. Show that the problem of determining whether or not $x \vdash^{*}_M y$ is und...
Rishi yadav
195
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
1
answer
1669
Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ ... that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ is said to be deterministic if it is an automaton as defined as defined, subject to ...
Rishi yadav
306
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1670
Peter Linz Edition 5 Exercise 12.1 Question 7,8 (Page No. 308)
$i)$ Show that there is no algorithm for deciding if any two Turing machines $M_1$ and $M_2$ accept the same language. $ii)$ How is the conclusion of $i$ affected if $M_2$ is a finite automaton$?$
$i)$ Show that there is no algorithm for deciding if any two Turing machines $M_1$ and $M_2$ accept the same language.$ii)$ How is the conclusion of $i$ affected if $M_2$...
Rishi yadav
145
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
1
answer
1671
Peter Linz Edition 5 Exercise 12.1 Question 6 (Page No. 308)
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the read-write head at the beginning of the computation$)?$”$ Is this a decidable question$?$
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the read-write head at the beginning of t...
Rishi yadav
461
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1672
Peter Linz Edition 5 Exercise 12.1 Question 5 (Page No. 307)
Show that there is no problem to decide whether or not an arbitrary Turing machine on all input.
Show that there is no problem to decide whether or not an arbitrary Turing machine on all input.
Rishi yadav
157
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1673
Peter Linz Edition 5 Exercise 12.1 Question 4 (Page No. 307)
In the general halting problem, we ask for an algorithm that gives the correct answer for any $M$ and $w$. We can relax this generality, for example by looking for an algorithm that works for all $M$ but only a ... that determines whether or not $(M,w)$ halts. Show that even in this restricted setting the problem is undecidable.
In the general halting problem, we ask for an algorithm that gives the correct answer for any $M$ and $w$. We can relax this generality, for example by looking for an alg...
Rishi yadav
254
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1674
Peter Linz Edition 5 Exercise 12.1 Question 3 (Page No. 307)
Show that the following problem is undecidable. Given any Turing machine $M, a\in \Gamma $ and $w \in \Sigma^{+}$, determine whether or not the symbol $a$ is ever written when $M$ is applied to $w$.
Show that the following problem is undecidable. Given any Turing machine $M, a\in \Gamma $ and $w \in \Sigma^{+}$, determine whether or not the symbol $a$ is ever written...
Rishi yadav
128
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
decidability
proof
+
–
0
votes
0
answers
1675
Peter Linz Edition 5 Exercise 12.1 Question 2 (Page No. 307)
$\text{Definition:}$ Let $w_M$ be a string that describes a Turing machine $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$, and let $w$ be a string in $M'$s alphabet. We will assume that $w_m$ and $w_M$ ... or not. Reexamine the proof of Theorem to show that this difference in the definition does not affect the proof in any significant way.
$\text{Definition:}$ Let $w_M$ be a string that describes a Turing machine $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$, and let $w$ be a string in $M’$s alphabet. We w...
Rishi yadav
159
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
decidability
theory-of-computation
proof
+
–
0
votes
0
answers
1676
Peter Linz Edition 5 Exercise 12.1 Question 1 (Page No. 307)
If the halting problem were decidable, then every recursively enumerable language would be recursive. Consequently, the halting problem is undecidable. Describe in detail how $H$ in given Theorem can be modified to produce $H^{\prime} $.
If the halting problem were decidable, then every recursively enumerable language would be recursive. Consequently, the halting problem is undecidable.Describe in detail ...
Rishi yadav
225
views
Rishi yadav
asked
Mar 14, 2019
Theory of Computation
peter-linz
peter-linz-edition5
decidability
theory-of-computation
+
–
0
votes
2
answers
1677
#TOC What will be the minimal DFA of this regular language?
Given L = { 0*1 + 0 + 1* + 10*1} where + symbol is UNION and NOT positive closure. Please draw the Minimal DFA for this.
Given L = { 0*1 + 0 + 1* + 10*1}where + symbol is UNION and NOT positive closure.Please draw the Minimal DFA for this.
iarnav
873
views
iarnav
asked
Mar 14, 2019
Theory of Computation
finite-automata
regular-expression
regs
theory-of-computation
+
–
2
votes
2
answers
1678
IDENTIFYING INHERENTLY AMBIGUOS GRAMMAR
How to identify if a grammar is inherently ambiguous grammar ??
How to identify if a grammar is inherently ambiguous grammar ??
s_dr_13
729
views
s_dr_13
asked
Mar 11, 2019
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
1679
#TOC what is the minimum pumping length of this regular language?
iarnav
2.1k
views
iarnav
asked
Mar 11, 2019
Theory of Computation
pumping-lemma
theory-of-computation
finite-automata
+
–
0
votes
1
answer
1680
No of strings of fixed length possible with a given grammar
What is the number of terminal string of length <= 6 generated by the CFG shown below? S -> 0A1 A -> BB1/B B ->A/0/1 Do you have any semantic method to solve such questions based on some pattern that can ... question it is 6,quite simple to derive but I am wondering what if it had been asked no of strings of length n Thanks
What is the number of terminal string of length <= 6 generated by the CFG shown below?S - 0A1A - BB1/BB ->A/0/1Do you have any semantic method to solve such questions bas...
s_dr_13
370
views
s_dr_13
asked
Mar 10, 2019
Theory of Computation
theory-of-computation
context-free-grammar
+
–
Page:
« prev
1
...
51
52
53
54
55
56
57
58
59
60
61
...
155
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register