Recent questions tagged michael-sipser

Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...

Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)

Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.

Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CF...

Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is...

Prove that the following two languages are undecidable.$OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$.$PREF...

Let$f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$for any natural number $x$. If you start with an inte...

Use Rice’s theorem, to prove the undecidability of each of the following languages.$INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite langu...

Rice’s theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language ha...

Rice’s theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language ha...

A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of th...

Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the in...

Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.

Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Tur...

Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$. Given an instance...

Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .

In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.

Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.

Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.

Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$,...

Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate t...

Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulat...

A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states....

Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any inp...

Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input s...

Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem...