Mastering Software Engineering: Diagrams, Models, and Testing Techniques

# Pushdown Automata: Explained

## Introduction

A context free grammar (CFG) can be implemented using push down automata (PDA), which is akin to how deterministic finite automata (DFA) are created for regular grammars.

A PDA can store unlimited amounts of information but a DFA can only store a finite quantity.

A PDA basically includes the following:

"Stack plus a finite state machine"

The three parts of a PDA are as follows:

- A cassette for input.
- A control system.
- An infinitely long stack.

A PDA might or might not be able to read input symbols, but every transaction requires it to read the top of the stack.

## 7-tuples are the formal definition of a PDA

**(Q, ∑,S, δ,q0,I,F)**

- Q is a finite number of states.
- ∑ is the input alphabet.
- S is a stack symbol.
- δ is the transition function: QX(∑U{e}) XSXQ
- q0 is the initial state (q0 belongs to Q).
- I is the initial state top symbol.
- F is a set of accepting states (F belongs to Q).

## Diagram

The diagram depicts a PDA transition from state q1 to state q2, which is denoted by the symbols a,b->c.

If an input string of 'a' is found in state q1, and the top symbol of the stack is 'b,' we pop 'b,' push 'c,' and go to state q2.