Question

Which of the following problem is undecidable

• A. Membership problem for CFL
• B. Membership problem for CSL
• C. Membership problem for regular set
• D. Membership problem for type 0 languages

Comments

D is it right

Answer 1

1)Membership problem for CFL----decidable

2)Membership problem for CSL----decidable

3)Membership problem for regular set====decidable

4)Membership problem for type 0 languages===undecidable

page no-7

http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture25.pdf

plz see

https://www.cs.virginia.edu/cs302/classes/class17.pdf

Comments

No. That does not seem correct. But here you can simply reduce from halting problem and assume it is known as undecidable.

---

ok sir..reduction is right answer... ok i will update...pdf..so that mr. sharma...can understand

---

sharmji ji plz check i have updated one more...pdf..may be it useful