2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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 PDA built from a context-free grammar $G$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what is The standard construction that will give us an automaton with three states.? $\endgroup$ – user7370059 May 17 '17 at 6:16
  • $\begingroup$ See e.g. the proof of Lemma 2.21 in the widely used textbook Introduction to the Theory of Computation by Michael Sipser. $\endgroup$ – Hans Hüttel May 17 '17 at 7:12
  • $\begingroup$ Perhaps you could expand on the standard construction, for those without access to this particular textbook? $\endgroup$ – Yuval Filmus May 17 '17 at 12:37
  • $\begingroup$ I have added a figure and some explanation. $\endgroup$ – Hans Hüttel May 17 '17 at 12:56
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.