Push Down Automaton | Sahithyan's Notes

An automaton with a stack. Used to recognize CFLs.

A 7-tuple: $(Q, \Sigma, \Gamma, q_0, Z_0, A, \delta)$

Here:

(Q, \Sigma, \Gamma, q_0, Z_0, A, \delta)

Here:

$Q$: states
$\Sigma$: input alphabet
$\Gamma$: stack alphabet
$q_0$: initial state
$Z_0$: initial stack symbol
$A$: accepting states
$\delta$: transition function

Stack

PDAs work with an internal stack, where elements can be pushed, popped, and replaced. The contents of the stack is expressed by a string of stack alphabet. By convention, left end of the string is the top element of the stack.

Stack is never empty. A special symbol $Z_0$ is always the bottom-most element. It’s never removed and no additional copies of $Z_0$ are pushed onto the stack.

Configuration

Represents current machine state. Denoted by $(q, x, \alpha)$ where:

(q, x, \alpha)

Here:

$q$: current state
$x$: remaining input
$\alpha$: stack contents

Element of $Q \times (\Sigma \cup {\Lambda}) \times \Gamma^*$ .

Transition

δ: Q \times (\Sigma \cup {\Lambda}) \times \Gamma^* \rightarrow \text{finite subsets of }Q \times \Gamma^*

Each transition maps a configuration to a set of finite subsets of $Q\times \Gamma^*$ .

$\delta (q, a, X) = (p, \beta)$ means, when the PDA has $X$ on the stack top, and gets $a$ as input, it moves to $p$ , replacing $X$ with $β$ .

Multi-step transition is denoted using $⊢^*$ .

Acceptance

2 modes.

Final State Acceptance

A string is accepted (by final state acceptance) iff it reaches a configuration with an accepting state.

(q_0, x, Z_0) ⊢^* (q, \Lambda, \alpha) \text{ where } q \in A

Input must be fully consumed. Stack may or may not be empty.

Empty Stack Acceptance

A string is accepted (by empty stack acceptance) iff it reaches a configuration with empty stack.

Non-Determinism

When multiple transitions are possible from the same configuration. It could:

consume input or not
consume input and multiple transitions for the same input

If not, the PDA is called a Deterministic PDA or DPDA in short. A CFL is called a Determinsitic CFL or DCFL if there exists a DPDA accepting the language.

An input string is accepted iff any paths reaches final state.

Computation Tree

Represents all possible PDA execution paths. Each node is a configuration. Each branch is a non-deterministic choice.