Question

Let . Show that$\mathit{P}\mathit{A}{\mathit{L}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$is decidable.

Short answer

$PA{L}_{DFA}$ is decidable.

Step-by-step solution

Explain PDA

Pushdown Automata is a finite automata that recognizes the context free languages. PDA has a extra memory that is called stack.

Step 2: Show that PALDFA is decidable.

Consider the given language . Construct a decider $\backslash$for $PA{L}_{DFA}$as follows,

Consider thar the turing machine T decides $E_{CFG}$.

D= “On input ,

1. Construct a PDA, $P_1$such that $L\left(P_1\right)=\left\{w|w \text{is} \text{a} \text{palindrome}\right\}$.

2. Construct a PDA ${P_1}^{\text{'}}$such that $L\left({P_1}^{\text{'}}\right)=L\left(P_1\right)\cap L\left(M\right)$

3. Convert ${P_1}^{\text{'}}$into an equivalent CFG G

4. Use T to check if $L\left(G\right)$is empty.

5. If L(G) is empty, reject. Else, accept.

In the above TM, Step 1 can be done in finite steps. Step 2 is based on Prob 2.18 and can be done in finite steps. Step 3 is the conversion of PDA into an equivalent CFG, which can be done in finite steps. Step 4 is done in finite steps, because the decider Dcan check whether the language of a CFG is empty. In summary, D runs in finite steps for any input, and is thus a decide

Therefore, it has been proved that $PA{L}_{DFA}$ is decidable.