# Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)

given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove correctness?

Any help appreciated.

Thanks!

From the NFA $N$ construction an equivalent context-free grammar $G$ using the standard construction for this, and then construct a PDA $M$ such that $L(M) = L(G)$. The standard construction will (given a suitable definition of the notion of pushdown automaton) give us an automaton with three states only.
The automaton will simulate the leftmost derivations of $G$, and its stack symbols include the set $V$ of nonterminals and the set $\Sigma$ of terminals as well as a bottom marker $\$$. Initially, \$$ is placed on the stack together with$S$. The main loop of the automaton is that involving the state$q_2$: If a nonterminal$A$appears as the topmost symbol on the stack and there is a production$A \rightarrow w$in$G$, then$A$is replaced by$w$in reverse. If a terminal$a$appears as the topmost symbol on the stack and the next input symbol to be read is also$a\$, then the automaton proceeds. Finally, if all input characters have been read and the bottom marker is the only symbol on the stack, the computation succeeds.