Question

Show that the following language is decidable APDA = { | M is a push down automata that accepts string w} Explain your steps.

Answer 1

A_PDA = { M | M is a push down automata that accepts string w }

A_PDA is a language which contains encoding of M_i and W_i where each M_i is a Push Down Automata (PDA) . The encoding of M_i and W_i means the representation of PDA and the string in binary values 0 (or) 1. This concept is same as the one used in Universal Turing Machine (UTM). So A_PDA can be understood as :

A_PDA = { <M₁,W_1>, <M₂,W_2> , <M₃,W_3> , <M4,W_4> , <M₅,W_5> , .............................. }

Here <M, W> represents that PDA M accepts the string W. To determine whether a string is acceptable by a language or not the following steps should be done

1. Conversion of given PDA to Context Free Grammar (CFG) (PDA to CFG Algorithm)
2. Conversion of obtained CFG to Chomsky Normal Form(CNF) Grammar (Simplification of CFG Algorithm)
3. Using this CNF Grammar to determine whether the string W is acceptable by it or not by Cocke-Younger-Kasami Algorithm (CYK Algortihm)

For steps 1,2 and 3 algorithms are already mentioned. All these algorithms take finite time. Either it is DPDA (or) NPDA, same three steps will have algorithms.

For a language to be decidable, it should be acceptable by a Halting Turing Machine (HTM), which is a type of TM that says whether the given string is acceptable by the TM or not . If the string is acceptable it says 'Yes' else it says 'No' unlike normal TM. Here also, the HTM will be programmed with three algorithms each corresponding to the steps above and each encoding will be given as an input. Then HTM determines whether M accepts W or not in finite amount of time. It can be visualized as :

For each and every string of A_PDA , algorithms are present to perform required action. So every string of A_PDA when given to HTM will give a valid result (yes or no). So A_PDA is decidable .