Unit 5 - Notes

CSE322 9 min read

Unit 5: PUSHDOWN AUTOMATA AND PARSING

1. Description and Model of Pushdown Automata (PDA)

A Pushdown Automaton (PDA) is essentially a Finite Automaton (FA) equipped with an auxiliary memory storage called a Stack. The stack operates on a Last-In-First-Out (LIFO) basis.

The Need for PDA

Finite Automata cannot handle languages that require unbounded memory (counting), such as $L = \{ a^n b^n \mid n \ge 1 \}$ . A PDA uses the stack to "remember" the number of $a$ 's by pushing them onto the stack and matching them with $b$ 's by popping.

The Model

A PDA consists of three main components:

Input Tape: Holds the input string. The input head reads one symbol at a time and moves right.
Finite Control: The "brain" of the automaton, similar to a DFA/NFA, which is in a specific state at any given time.
Stack: An infinite tape that can hold symbols. The machine can:
- Push: Add a symbol to the top.
- Pop: Remove a symbol from the top.
- Read: Only the top symbol of the stack is accessible.

2. Representation of PDA

Formally, a PDA is defined as a 7-tuple:

M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)

Where:

$Q$ : A finite set of states.
$\Sigma$ : A finite set of input symbols (Input Alphabet).
$\Gamma$ : A finite set of stack symbols (Stack Alphabet). Note that $\Sigma$ and $\Gamma$ can overlap.
$q_0$ : The initial state ( $q_0 \in Q$ ).
$Z_0$ : The initial stack symbol ( $Z_0 \in \Gamma$ ), which is on the stack at the start.
$F$ : The set of final/accepting states ( $F \subseteq Q$ ).
$\delta$ : The transition function, defined as:

Interpretation: $\delta(q, a, X) = \{ (p, \alpha) \}$ means:
- Current state is $q$ .
- Input symbol read is $a$ (or $\epsilon$ for empty move).
- Top of stack is $X$ .
- The machine moves to state and replaces with string on the stack.
  - If $\alpha = \epsilon$ , it is a Pop operation.
  - If $\alpha = X$ , the stack remains unchanged.
  - If $\alpha = YX$ , it is a Push operation (pushing $Y$ ).

Instantaneous Description (ID)

An ID describes the configuration of the PDA at a specific moment. It is represented as a triplet:

(q, w, \gamma)

$q$ : Current state.
$w$ : Remaining input string.
$\gamma$ : Current stack content (leftmost symbol is top of stack).

3. Acceptance by PDA

A PDA can define a language in two distinct ways. Both methods are equivalent in power.

A. Acceptance by Final State

The PDA accepts string $w$ if, after reading the entire input, the machine enters a state belonging to $F$ . The stack content does not matter.

L(M) = \{ w \mid (q_0, w, Z_0) \vdash^* (q_f, \epsilon, \alpha) \text{ for some } q_f \in F, \alpha \in \Gamma^* \}

B. Acceptance by Empty Stack

The PDA accepts string $w$ if, after reading the entire input, the stack becomes empty. The final state of the control does not matter.

N(M) = \{ w \mid (q_0, w, Z_0) \vdash^* (q, \epsilon, \epsilon) \text{ for any } q \in Q \}

Note: If a language is accepted by empty stack, there exists a PDA that accepts it by final state, and vice versa.

4. Pushdown Automata: NDPDA and DPDA

Non-Deterministic PDA (NDPDA)

In an NDPDA, for a given state, input symbol, and stack symbol, there may be multiple possible moves (transitions).

Characteristic: The transition function maps to a subset of $Q \times \Gamma^*$ (a set of possibilities).
Power: NDPDAs accept the full class of Context-Free Languages (CFLs).

Deterministic PDA (DPDA)

A DPDA has at most one legal move for any configuration.

Conditions for Determinism:
1. $|\delta(q, a, X)| \le 1$ for all $q \in Q, a \in \Sigma \cup \{\epsilon\}, X \in \Gamma$ .
2. If $\delta(q, \epsilon, X)$ is defined (non-empty), then $\delta(q, a, X)$ must be empty for all $a \in \Sigma$ . (No conflict between reading an input and making an $\epsilon$ -move).
Power: DPDAs accept Deterministic Context-Free Languages (DCFLs).

Comparison: Deterministic vs. Non-Deterministic

Feature	Deterministic PDA (DPDA)	Non-Deterministic PDA (NDPDA)
Moves	Single unique move for any config.	Multiple choices permitted.
Language Class	Accepts DCFLs.	Accepts all CFLs.
Ambiguity	Handles unambiguous grammars only.	Can handle ambiguous grammars.
Power	Less powerful than NDPDA.	More powerful than DPDA.
Equivalence to FA	DPDA $\neq$ NDPDA.	NFA $\equiv$ DFA, but this does not hold for PDAs.

Crucial Note: Unlike Finite Automata where DFA and NFA are equivalent, NDPDAs are strictly more powerful than DPDAs.

5. Context-Free Languages and PDA

The Fundamental Theorem

There is a strong equivalence between Context-Free Grammars (CFG) and Pushdown Automata:

For every Context-Free Language $L$ (generated by a CFG), there exists an NDPDA that accepts $L$ .
For every PDA $M$ , the language $L(M)$ accepted by $M$ is a Context-Free Language.

Equivalence Construction

1. CFG to PDA

Given a CFG $G = (V, T, P, S)$ , we construct a PDA that simulates the leftmost derivation of $G$ .

Start: Push $S$ onto the stack.
Transitions:
- If the stack top is a Variable $A$ : Pop $A$ and push the right-hand side of a production $A \to \alpha$ (non-deterministically).
- If the stack top is a Terminal $a$ : Read input $a$ . If they match, pop $a$ . If not, crash (reject).

2. PDA to CFG

Given a PDA, we can construct a grammar where variables represent moving between states while popping specific symbols from the stack. The variables are usually of the form $[p, A, q]$ , representing a computation starting in state $p$ with $A$ on the stack and ending in state $q$ with $A$ popped.

6. Closure Properties of CFLs

Context-Free Languages are closed under:

Union: If $L_1$ and $L_2$ are CFLs, $L_1 \cup L_2$ is a CFL.
Concatenation: If $L_1$ and $L_2$ are CFLs, $L_1 \cdot L_2$ is a CFL.
Kleene Star: If $L$ is a CFL, $L^*$ is a CFL.
Reversal: If $L$ is a CFL, $L^R$ is a CFL.
Homomorphism and Inverse Homomorphism.

Context-Free Languages are NOT closed under:

Intersection: If and are CFLs, is not necessarily a CFL.
- Example: $L_1 = \{a^n b^n c^m\}$ and $L_2 = \{a^m b^n c^n\}$ are CFLs, but $L_1 \cap L_2 = \{a^n b^n c^n\}$ is not.
Complementation: If $L$ is a CFL, $\Sigma^* - L$ is not necessarily a CFL. (This follows from De Morgan's laws and non-closure under intersection).
Difference: $L_1 - L_2$ is not necessarily a CFL.

Note: DCFLs (Deterministic CFLs) are closed under Complementation but not under Union or Intersection.

PARSING

7. Introduction to Parsing

Parsing (or Syntax Analysis) is the process of checking whether a given string of symbols can be generated by a specific grammar. It involves constructing a Parse Tree (or Derivation Tree) for the input string.

Goals of Parsing

Check syntax validity.
Produce a parse tree to be used for semantic analysis and code generation.

8. Classification of Parsing Techniques

Parsing is broadly classified into two categories based on how the parse tree is constructed:

A. Top-Down Parsing

Direction: Starts from the Start Symbol ( $S$ ) and attempts to derive the input string $w$ .
Tree Construction: Builds the tree from the Root down to the Leaves.
Method: Uses Leftmost Derivation.
Challenges:
- Backtracking: If a chosen production rule turns out to be wrong, the parser must undo steps.
- Left Recursion: If $A \to A\alpha$ , the parser may enter an infinite loop. This must be eliminated.
- Left Factoring: Required when multiple productions start with the same symbol (e.g., $A \to \alpha\beta_1 \mid \alpha\beta_2$ ).

B. Bottom-Up Parsing

Direction: Starts from the input string $w$ and attempts to reduce it to the Start Symbol ( $S$ ).
Tree Construction: Builds the tree from the Leaves up to the Root.
Method: Uses Reverse of Rightmost Derivation.
Mechanism: Uses "Shift" (move input to stack) and "Reduce" (replace substring on stack with a non-terminal) operations. This is often called Shift-Reduce Parsing.
Handle: The substring currently being reduced is called the "handle".

9. LL(k) Grammars and Properties

LL(k) parsers are a type of Deterministic Top-Down parser.

First 'L': Scans input from Left to right.
Second 'L': Produces a Leftmost derivation.
'k': Uses k symbols of lookahead to make decisions.

LL(1) Grammar

The most common form is LL(1). A grammar is LL(1) if the parsing table has no multiple entries (no conflicts).

Properties/Conditions for LL(1):
For any two distinct productions $A \to \alpha$ and $A \to \beta$ :

$FIRST(\alpha)$ and $FIRST(\beta)$ must be disjoint sets.
If $\epsilon \in FIRST(\beta)$ , then $FIRST(\alpha)$ and $FOLLOW(A)$ must be disjoint.

Limitations:

Cannot handle Left Recursive grammars.
Cannot handle Ambiguous grammars.

10. LR(k) Grammars and Properties

LR(k) parsers are a type of Deterministic Bottom-Up parser.

'L': Scans input from Left to right.
'R': Constructs a Rightmost derivation in reverse.
'k': Uses k symbols of lookahead.

Types of LR Parsers

LR(0): No lookahead. Simplest but least powerful.
SLR(1) (Simple LR): Uses FOLLOW sets for reduction decisions. More powerful than LR(0).
LALR(1) (Look-Ahead LR): Merges states of LR(1) to reduce table size. Standard in tools like YACC/Bison.
CLR(1) (Canonical LR): Full lookahead. Most powerful but has very large parsing tables.

Properties of LR Grammars

Power: LR(k) grammars cover strictly more languages than LL(k). All LL(k) grammars are LR(k), but not vice versa.
Detecting Errors: LR parsers detect syntax errors as soon as possible on a left-to-right scan.
Determinism: They handle virtually all deterministic context-free languages.
Conflicts: If a grammar is not LR, the parsing table will have conflicts:
- Shift-Reduce Conflict: Parser doesn't know whether to shift input or reduce stack.
- Reduce-Reduce Conflict: Parser has two valid rules to reduce the stack content.

Summary Comparison: Top-Down vs Bottom-Up

Feature	Top-Down (LL)	Bottom-Up (LR)
Start Point	Root ( $S$ )	Leaves (Input String)
Derivation	Leftmost	Reverse Rightmost
Recursion Support	Cannot handle Left Recursion	Handles Left Recursion
Lookahead	Usually 1 (LL(1))	Usually 1 (LALR, SLR)
Complexity	Easier to implement manually (Recursive Descent)	Harder to implement manually; uses tools
Power	Less powerful	More powerful

Unit 4

Unit 6