Register

Recent questions tagged proof

0 votes
0 answers
213
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$?$
User Avatar
0 votes
0 answers
214
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 ...
User Avatar
0 votes
0 answers
220
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...
User Avatar
0 votes
0 answers
224
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...
User Avatar
1 votes
1 answer
225
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.
User Avatar
0 votes
0 answers
227
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...
User Avatar
3 votes
0 answers
238
Minimum No. of vertices required
Prove the following for graph $G$. When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ ... $k$.
Prove the following for graph $G$.When length of the shortest cycle in a graph is $k \geq 3$ and the minimum degree of the graph is $d$, then $G$ has minimum $\begin{alig...
User Avatar
Page: