Questions tagged [decidability]
The decidability tag has no usage guidance.
26
questions
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 ...
