Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
14 views

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

Let A be a nonempty alphabet, $X ⊆ A^*$ a decidable set, and $Y ⊆ A^*$ be a semi-decidable set. We assume that $Y ⊆ X$ and that $X \setminus Y ⊆ A^*$ is semi-decidable. Show that then the set Y ⊆ A∗ ...
0
votes
0answers
27 views

If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?

There is a lemma in our textbook that asks us to prove the following: If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable I tried proving this by saying that if $L_1 \leq_m L_2$, ...
0
votes
1answer
37 views

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

Obviously it is an open question if $3$-SAT can be decided in a polynomial amount of time. But what results do we know about its recognizabilty? Can $3$-SAT be recognized in a polynomial amount of ...
0
votes
0answers
25 views

Decidability of the language of a regular expression being a subset of a given context free language

Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG. Is it decidable that G accepts whatever the regular expression does? In other words, ...
0
votes
0answers
40 views

Complement of a context free language

Consider the context-free language of balanced parentheses of three kinds: $$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$ What will be the ...
1
vote
1answer
40 views

Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
0
votes
0answers
19 views

Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
-1
votes
1answer
41 views

Does Turing machine move left on particular input?

We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
0
votes
1answer
78 views

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

Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
0
votes
0answers
32 views

Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]

We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
0
votes
1answer
167 views

Why REC languages is undecidable under emptiness and finiteness?

Membership problem of Recursive languages are decidable. My approach: Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in ...
0
votes
0answers
55 views

Whether $L(G)=L(R)$ is decidable for DCFL and CFL?

Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not? My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
1answer
102 views

Rice theorem could apply except RE language?

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages. $Q_1:$ So ...
0
votes
2answers
165 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
0
votes
1answer
46 views

Why finiteness problem of CFL is decidable?

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
0
votes
1answer
79 views

Reduction from undecidability, decidability to decididabilty

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
0
votes
0answers
29 views

Is this language in RE?

Given the following language: $$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$ I need to determine it's compuation class(R or RE). I used Rice Theorem as follows to ...
0
votes
0answers
18 views

Loop in control flow graph of a program versus checking whether program goes into infinite loop or not

Which of these is true or false. 1)If Control Flow graph(CFG) doesn't contain any loop, the program will never go into infinite loop. 2)If CFG contains loop, the program may or may not go into ...
-1
votes
1answer
50 views

How to determine whether this language is regular?

I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not: $$ L_1=\{w\in\Sigma^*|for \ 1 \...
0
votes
1answer
34 views

Prove decidable

L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s } T = "On input where M is encoded DFA" ...
0
votes
0answers
32 views

The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can. First, here is an hypothesis: diagonalization is syatematically used to prove ...
2
votes
1answer
44 views

Effectively decidable vs. noneffectively (or ineffectively) decidable

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I ...
1
vote
2answers
80 views

Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable. To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
1
vote
1answer
38 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
-5
votes
1answer
365 views

Could H correctly decide that P never halts?

Could H be adapted to correctly decide that P never halts? See also: The Halting problem proof is wrong? The standard pseudo-code halting problem template "proves" that the halting problem ...
4
votes
1answer
1k views

A language is Turing recognizable iff it is a projection of a decidable language

I was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to ...