4 votes
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 ...
user avatar
  • 23.9k
3 votes
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 ...
user avatar
  • 34.7k
3 votes
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 ...
user avatar
3 votes
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 ...
user avatar
  • 34.7k
2 votes

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 ...
user avatar
2 votes

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 ...
user avatar
  • 27.7k
2 votes
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.
user avatar
  • 13.7k
2 votes
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 ...
user avatar
  • 34.7k
2 votes
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 ...
user avatar
2 votes
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 ...
user avatar
  • 34.7k
2 votes

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 ...
user avatar
  • 11.3k
2 votes
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 23.9k

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