Questions tagged [decidability]

The tag has no usage guidance.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
43 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
77 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
0answers
28 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
15 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 ...
0
votes
0answers
23 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 ...
-1
votes
1answer
28 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 ...
-1
votes
0answers
22 views

TM decidable or undecidable problem?

Question: Explain why the following problems are decidable or undecidable (Using rice's theorem where possible). Does the language accepted by a Turing machine contain an even-length word? Holds a ...