Register

Decidability Doubt

2,298 views
0 0 votes
Can someone explain in simple words 'Membership problem is undecidable"?

1 Answer

1 1 vote

In simple words Decidability of Membership Problem means that : "For a language L , given a string W we can always check whether W belongs to L or W does not belongs to L in finite amount of time i.e an algorithm exists such that given a string W it will always say YES or NO ".

Regular Languages : "Membership problem is decidable" .A Finite Automata can be drawn and W can be traced starting from initial state, if it reaches final state then W is member else not.

Context Free Language: "Membership problem is decidable": CYK algorithm exists

Reursive language: A language L is Recursive iff  their exists a Halting TM M such that it accepts all W belong to L and rejects all W that does not belongs to L.thus  "Membership problem is decidable"

Recursive Enumerable Language : "Membership problem is Undecidable".  their exists a  TM M such that it accepts all W belong to L and Halts but if W does not belong to L ,the TM M might not be able to reject and does not halt. 

Voting & Accepting an answer helps improve the community
← Previous · GATE SELFNext → · minimum number of NO...
← Previous in category · finte automataNext in category → · TOC DECIDABILITY
Position:
Show:

Related questions

0 0 votes
1 1 answer
1.5k
1.5k views
ajaysoni1924 asked Jul 15, 2019
1,481 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
694
694 views
Mk Utkarsh asked Nov 23, 2018
694 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,...
0 0 votes
0 0 answers
544
544 views
aditi19 asked Oct 29, 2018
544 views
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
1 1 vote
2 2 answers
1.0k
1.0k views
rahul sharma 5 asked Jan 15, 2017
1,043 views
Doubt in GateCse Decidability Blog
In the deciadability chart mentioned on http://gatecse.in/grammar-decidable-and-undecidable-problems/The undecidable problems mentioned here are semidecidable(RE but not ...