O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required