Question

How can a finite state machine be converted into a push down automata?

(a) By including a push-down stack

(b) By including a push-down stack with Push() function

(c) By including a push-down stack with Pop() function

(d) By including a push-down stack with Push() and Pop() function

I had been asked this question in an online quiz.

This intriguing question originated from Software Architecture Tradeoffs topic in chapter Technology Tradeoffs in Software Defined Radio of Cognitive Radio

Answer 1

Right option is (c) By including a push-down stack with Pop() function

The explanation is: A finite state machine be converted into a push down automata by including a push-down stack with Push() and Pop() function. Push-down automata supports unlimited number of states. The availability of stack space and time taken to reach certain states are challenges for push-down automata.