Register

decidability

1,696 views
0 0 votes

please someone explain what are these problems and how to solve these problems for every language with proper explanation?

  1. MEMBERSHIP PROBLEM
  2. EMPTINESS PROBLEM
  3. COMPLETENESS PROBLEM
  4. EQUILITY PROBLEM
  5. SUBSET PROBLEM
  6. DISJOINTNESS PROBLEM
  7. IS GIVEN LANGUAGE REGULAR 
  8. FINITENESS PROBLEM

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Page replacement imp...Next → · Gateforum Test Serie...
← Previous in category · Regular expressionsNext in category → · Closure Properties
Position:
Show:

Related questions

1 1 vote
0 0 answers
905
905 views
amitarp818 asked Dec 28, 2023
905 views
Decidability
L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t understand why th...
0 0 votes
1 1 answer
1.5k
1.5k views
ajaysoni1924 asked Jul 15, 2019
1,500 views
Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...
0 0 votes
0 0 answers
699
699 views
Mk Utkarsh asked Nov 23, 2018
699 views
Decidability Doubt
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$$L_2 = \{ \text{<M>} | \ \text{M is a TM,...
1 1 vote
0 0 answers
3.2k
3.2k views
Na462 asked Nov 14, 2018
3,210 views
Decidability