Tuesday 15 April 2014

Sipser 4.10 Show INFINITE is decidable.

Solution:

Turing machine INFINITE<PDA>:
On input <M>,
1. Convert given M to CFL using algorithm for converting PDA to CFL.
2. Run INFINITE<CFL> , If it accepts then accept, else if it rejects reject.

No comments:

Post a Comment