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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.
The idea of the construction is to keep the current state as the symbol at the top of the stack. At each step, you pop the symbol at the top of the stack (the current state) and read a single character, and push the state to which the DFA transitions to the stack.
I leave the rest of the details to you.