# Tagged Questions

29 views

### Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
42 views

### Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
469 views

### Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...
46 views

### Palindromes and linear grammars

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
19 views

### Decidability of fullness of intersection of a CSL with a regular language

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable? $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$ ...
154 views

### Is the image of a total, non-decreasing function decidable?

This is an exercise I've been struggling with for a while: Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of ...
162 views

### Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhillâ€“Nerode theorem which provides a necessary and sufficient ...
45 views

### Using Rice's Theorem Correctly [duplicate]

I'm currently learning about Rice's Theorem, and I'm having a bit of trouble understanding when I can and cannot use it. It's my understanding that Rice's Theorem can only be applied to something if ...
79 views

### Recursive language with non-recursive subsets

I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question: Recursive language with non-recursive subsets. Does ...
667 views

### Undecidable among these for turing machine

Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation? It is undecidable, whether an arbitrary ...
526 views

### Do undecidable languages exist in constructivist logic?

Constructivist logic is a system which removes the Law of the Excluded Middle, as well as Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't ...
331 views

### Is it possible that the union of two undecidable languages is decidable?

I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$. I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't ...
136 views

### Is the universe problem for one-counter automata with restricted alphabet size undecidable?

Consider the following universe problem. The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$. In [1], ...
570 views

### How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

How do I show that the problem of deciding whether a PDA accepts some string of the form $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable? I have tried to reduce this problem to another undecidable ...
108 views

162 views

### Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

From this statement As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language. I would like to understand why similar reasoning ...
1k views

### Is there an undecidable finite language of finite words?

Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable? I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, (\$N ...