Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points


    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points


    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

Recent questions tagged decidability

0 votes
2 answers 12 views
L=a language M= a TM Lc= complement of L 1) L={<M> | M is a TM, encoded with some alphabet } ; L is recursive 2) L=set of all cfls generated by some cfg; => L is recursive enumerable but not recursive , Lc is not Recursive ... is Recursively Enumerable but Not Recursive I BELIEVE THE ABOVE STATEMENTS TO BE TRUE / CORRECT please somebody verify and reply please do reply ASAP THANKING YOU.
asked 2 days ago in Theory of Computation BLACK_CLOUD 14 points 12 views
0 votes
3 answers 29 views
Is it decidable that a Turing Machine will ever leave the start state on any input?
asked Sep 11 in Theory of Computation Sukhbir Singh 7 points 29 views
0 votes
1 answer 16 views
Let G1 be a context free grammar and G2 a regular grammar. Is the problem decidable? $L(G1) \cap L(G2)= \phi$ Let L1 be a regular language and G a context free grammar. Is the problem decidable? $L1\subseteq L(G)$ 3. Let G1 and G2 be grammars with G1 regular. Is the problem decidable when: $L(G1)=L(G2)$ * G2 is unrestricted * G2 is context free * G2 is regular?
asked Sep 7 in Theory of Computation कुशाग्र गुप्ता 46 points 16 views
0 votes
0 answers 14 views
$L = \{ <M> | \text{M is a TM that halts on all inputs and L(M) = L’ for some undecidable language L’} \}$ Then $L$ is decidable and recursive decidable and non-recursive undecidable and recursively enumerable undecidable and non-recursively enumerable
asked Aug 26 in Theory of Computation Satbir 2.1k points 14 views
0 votes
1 answer 36 views
For the following language, state whether language is (I) recursive, (II) recursively enumerable but not recursive, or (III) not recursively enumerable. Prove your answer. $L_{11} = \{<M_{1}, M_2> | \text{ M}_1 \text{and M}_2 \text{ are two TMs}, \text{and } \epsilon \in L(M_1) \backslash L(M_2) \}$
asked Aug 22 in Digital Logic Mk Utkarsh 26 points 36 views
0 votes
0 answers 21 views
Please some explain this question with diagram. the correct answer is A.
asked Jul 8 in Theory of Computation a009ik 7 points 21 views
To see more, click for the full list of questions or popular tags.