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

1 Answer

1 votes
1 votes

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. 

Related questions

0 votes
0 votes
0 answers
3
aditi19 asked Oct 29, 2018
250 views
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?