1,270 views
2 votes
2 votes
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 ?

2 Answers

Best answer
3 votes
3 votes

. 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.

selected by
1 votes
1 votes
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.

Related questions

–2 votes
–2 votes
0 answers
4
Anmol Verma asked Dec 4, 2016
907 views
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??