5

Push Down Automata

  • The concept PushDown Automata (PDAs) is useful in designing parsers or syntax analysers. A parser verifies the syntax of the text. Parsing is a part of the compilation process. So, knowledge of PDAs is useful in compiler design.

In this chapter, we introduce PushDown Automata (PDAs) and discuss how the language is accepted. Theorems that show the equivalence of PDA and context free languages are discussed. Equivalence of PDA that accepts language using empty stack and reaching to final state is explained. Finally, how to use PDA as a parser is described.

The automata that we have discussed so far have very limited memory capabilities. It cannot recognize all CFLs. We understand that this is because Finite Automata have ...

Get Formal Languages and Automata Theory now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.