# Tag Info

Accepted

### Why REC languages is undecidable under emptiness and finiteness?

To decide whether a language is empty you'd have to run $M$ on all possible input strings and verify that $M$ always rejects. How are you going to do that in a way that ensures that your algorithm ...
• 23.9k
Accepted

### Language of Turing machines that go through some configuration infinitely many times on empty input

No, $L$ is not decidable. Summary (a complete proof for experienced readers): Given a Turing-machine $T$, we can construct algorithmically Turing-machine U that simulates $T$. Moreover, $U$ will ...
• 34.7k
Accepted

### Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?

Here is the idea in a nutshell: Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \{t\}$, where $t$ is the transcript of the ...
• 270k
Accepted

### For any two languages A and B there exists J such that both A and B are Turing reducible to J

I don't think this proposition can be proved using the hierarchy of languages as illustrated in the question alone. That hierarchy of languages is too coarse to imply directly any implication between ...
• 34.7k

### Regularity of CFG and DCFL

Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class. Regularity of the language ...
• 270k

### Regularity of CFG and DCFL

Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement. The ...
• 27.7k
Accepted

### Why finiteness problem of CFL is decidable?

The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$. This is easy to check.
• 13.7k
Accepted

### A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function

"If $L$ is the image of some strictly increasing computable function there's a 1-1 correspondence between the natural numbers and the words in $L$". This is a key observation. You might have ...
• 34.7k
Accepted

### Useless states in a PDA

Your formulation of the language is wrong. Your language is a collection of pushdown automata. A PDA $M$ is in your language if it has no useless states. This means that for every state $q$, there is ...
• 270k
Accepted

### If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

There is no definitive answer. If predicate $P$ is partially-decidable, $\neg P$ can be decidable, partially-decidable or undecidable. Let $P(n)$ be "is $n>1$?". $P$ is partially ...
• 34.7k

### Decidability of a context free Grammar

"Redness" is decidable, because the alphabet of a context-free grammar is finite (by definition), and therefore the set of strings exactly three characters long starting with ...
• 11.3k
Accepted

### Can 3-SAT be recognized in less than exponential time?

This problem stays an open problem (at least using the intuitive definition of "recognizable in poly time" - either running in poly time or looping forever). Consider there is such a TM that ...
• 10.9k
1 vote
Accepted

### Decidability for intersection of context free and regular languages

The first one you have solved correctly. Emptiness of context-free languages is decidable. For the second, we can rewrite $\bar L \cap R = \varnothing$ into $R\subseteq L$. This is undecidable (even ...
• 27.7k
1 vote
Accepted

### Show that $Y \subseteq A^*$ is decidable

Let $x \in A^*$ be your input string. We can check that $x \in X$ and, if that is not the case, reject immediately (since we know that $x \not\in X \supseteq Y$). Now, we know that exists a Turing ...
• 23.9k
1 vote
Accepted

### Reduction from undecidability, decidability to decididabilty

If $L_1$ is decidable and $L_2$ is decidable then it is not necessarily true that $L_1 \le_m L_2$. Consider for example any $L_1$ distinct from $\emptyset$ and pick $L_2 = \emptyset$. In general, if \$...
• 23.9k

Only top scored, non community-wiki answers of a minimum length are eligible