Are the below two problems decidable ?

Question

1. A turing machine prints a specific letter .

2.If L is CFL then L' is also CFL .

For the second one ,it is known that L' will not be CFL but then why can't we design any algorithm for it ,since it is true that complement of CFL will never be true so then what is the essence here with respect to talking about decidable and undecidable ?

Answer 1

. A turing machine prints a specific letter .

This problem is redusable to state entry problem. i.e. TM print specific letter if it enter on perticular state since state entry problem is undecidable so it is also.

Comments

For the b part you can see here: 

http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf

But your understanding of "not closed" is wrong. A SET not closed under an operator means when we operate the set elements we might  get an element not in set. So, CFL being not closed under complement does not mean complement of a CFL is not CFL. 

---

Ok sir  got it now never use it.

---

sorry, that comment was not for you. But I guess you also had this confusion..

---

One my post u asked me about closed .. so i think this was for me..:)

Answer 2

Does turing machine ever enter state q and print a string a or simply print a specific letters always undecidable problem?

Complementation is not closed under CFL as well as it is a undecidable problem.