7
Pushdown Automata
Introduction
Pushdown automata (in short PDA) is the machine format of the context-free language. It is the same as finite automata with the attachment of an auxiliary amount of storage as stack. Already, we have discussed the limitations of finite automata. Pushdown automata is designed to remove those limitations. Remember the example of anbn, which is not recognizable by the finite automata due to the limitation of memory, but pushdown automata can memorize the number of occurrences of ‘a’ and match it with the number of occurrences of ‘b’ with the help of the stack. In this chapter, we shall learn about the mathematical representation of PDA, acceptance by a PDA, deterministic PDA, non-deterministic PDA, conversion of ...
Get Introduction to Automata Theory, Formal Languages and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
