Register

Materials:

Recent questions tagged decidability

0 0 votes
0 0 answers
315
315 views
Peter Linz Edition 5 Exercise 12.5 Question 1 (Page No. 323)
Consider the language $L = \{ww:w\in\{a, b\}^+\}$.Discuss the construction and efficiency of algor...
User Avatar
0 0 votes
1 1 answer
565
565 views
Peter Linz Edition 5 Exercise 12.4 Question 8 (Page No. 321)
Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted,$\text(b)$ when $G_2$ is context-free...
User Avatar
0 0 votes
1 1 answer
548
548 views
Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$
User Avatar
0 0 votes
0 0 answers
331
331 views
Peter Linz Edition 5 Exercise 12.4 Question 6 (Page No. 321)
Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation ...
User Avatar
0 0 votes
1 1 answer
426
426 views
Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.
User Avatar
0 0 votes
0 0 answers
298
298 views
Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in The...
User Avatar
0 0 votes
0 0 answers
266
266 views
Peter Linz Edition 5 Exercise 12.4 Question 3 (Page No. 321)
Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is context-free$”$ is undecidable.
User Avatar
0 0 votes
0 0 answers
295
295 views
Peter Linz Edition 5 Exercise 12.4 Question 2 (Page No. 321)
Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for context-free grammars $G_1,\space G_2$.
User Avatar
0 0 votes
0 0 answers
290
290 views
Peter Linz Edition 5 Exercise 12.4 Question 1 (Page No. 320)
$\text{Theorem}:$ There exists no algorithm for deciding whether any given context-free grammar is ambiguous.Prove the claim made in Theorem that $G_A$ and $G_B$ by thems...
User Avatar
0 0 votes
0 0 answers
473
473 views
Peter Linz Edition 5 Exercise 12.3 Question 6 (Page No. 318)
The correspondence pair $(A, B)$ is said to have an even PC solution if and only if there exists a nonempty sequence of even integers $i,j,..k$ such that $w_iw_j...w_k = ...
User Avatar
0 0 votes
0 0 answers
433
433 views
Peter Linz Edition 5 Exercise 12.3 Question 5 (Page No. 317,318)
Show that the following modifications of the Post correspondence problem are undecidable.$\text(a)$ There is an MPC solution if there is a sequence of integers such that ...
User Avatar
0 0 votes
0 0 answers
544
544 views
Peter Linz Edition 5 Exercise 12.3 Question 4 (Page No. 317)
Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable$?$
User Avatar
0 0 votes
0 0 answers
373
373 views
Peter Linz Edition 5 Exercise 12.3 Question 3 (Page No. 317)
Show that for $|\Sigma| = 1$, the Post correspondence problem is decidable, that is, there is an algorithm that can decide whether or not $(A, B)$ has a $\text{PC}$ solut...
User Avatar
0 0 votes
0 0 answers
294
294 views
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 ...
User Avatar
0 0 votes
0 0 answers
368
368 views
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$?$
User Avatar
0 0 votes
0 0 answers
330
330 views
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 princi...
User Avatar
0 0 votes
0 0 answers
316
316 views
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) \spa...
User Avatar
0 0 votes
0 0 answers
351
351 views
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\ca...
User Avatar
0 0 votes
0 0 answers
1.0k
1.0k views
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$$?$
User Avatar
0 0 votes
0 0 answers
454
454 views
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$?$
User Avatar
0 0 votes
0 0 answers
369
369 views
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.
User Avatar
0 0 votes
0 0 answers
345
345 views
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 unde...
User Avatar
0 0 votes
0 0 answers
317
317 views
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 $\tex...
User Avatar
0 0 votes
0 0 answers
333
333 views
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.
User Avatar
0 0 votes
0 0 answers
269
269 views
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...
User Avatar
0 0 votes
0 0 answers
272
272 views
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 wit...
User Avatar
1 1 vote
1 1 answer
590
590 views
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.
User Avatar
0 0 votes
0 0 answers
272
272 views
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.
User Avatar
0 0 votes
0 0 answers
239
239 views
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 s...
User Avatar
Page: