Chapter 10 - Grammars and Chomsky Hierarchy

The theory of formal languages is a cornerstone of theoretical computer science, with profound connections to linguistics and even evolutionary biology. While our previous computational models, such as finite automata and Turing machines, were primarily conceived as acceptors of languages (recognizing whether a given word belongs to a language), grammars offer an alternative perspective: they are mechanisms for generating (producing) words.

Grammars provide a finite way to describe potentially infinite languages. For linguists, they are crucial for formally describing the syntax of natural languages. In computer science, grammars, especially context-free grammars, are central to defining the syntax of programming languages and are indispensable in compiler construction. (They allow us to precisely define the valid structure of code, enabling compilers to parse and understand programs.) From a computability standpoint, the most general type of grammars (Type-0) are as powerful as Turing machines, further reinforcing Church’s thesis.

This chapter will introduce the fundamental concept of grammars, explain their generative mechanism, and classify them according to the Chomsky Hierarchy. We will explore each type of grammar, relating its generative power to the corresponding automaton model we’ve studied.

10.1 Aims

By the end of this chapter, you will be able to:

• Understand the Concept of Grammars: Grasp how grammars axiomatically define and generate languages.
• Formally Define Grammars: Understand the components of a grammar (nonterminals, terminals, production rules, start symbol) and the process of derivation.
• Classify Grammars by the Chomsky Hierarchy: Differentiate between Type-0 (unrestricted), Type-1 (context-sensitive), Type-2 (context-free), and Type-3 (regular) grammars based on their rule restrictions.
• Relate Grammars to Automata: Understand the equivalence between regular grammars and finite automata, and context-free grammars and pushdown automata.
• Apply Normal Forms: Understand Chomsky and Greibach normal forms for context-free grammars.
• Prove Non-Context-Freeness: Utilize the Pumping Lemma for Context-Free Languages and Ogden’s Lemma to demonstrate that certain languages are not context-free.

---

10.2 The Concept of Grammars

Grammars provide an axiomatic method for defining classes of objects. Just as Boolean formulas can be defined recursively, languages can be defined by a set of rules that generate their words.

Generation Procedure for $L=\{a^i{b}^i\mid i\in \mathbb{N}\}$

Consider the following rules for generating a language $L$ over {a, b}:

1. $\lambda \in L$.
2. If $x\in L$, then $axb\in L$.
3. No other words belong to $L$.

Starting with $\lambda$, applying rule (2) once yields $ab$, twice yields $a^2{b}^2$, and so on. This procedure generates exactly the language $L=\{a^i{b}^i\mid i\in \mathbb{N}\}$.

This idea is formalized using terminal symbols (the alphabet of the language, which are the final characters in a generated word), nonterminal symbols (variables that are replaced during generation, acting as placeholders for structures), production rules (the rewrite rules), and a start symbol.

Definition 10.1 (Grammar)

1. A grammar $G$ is a 4-tuple $G=({\Sigma }_N,{\Sigma }_T,P,S)$, where: a. ${\Sigma }_N$ is the nonterminal alphabet (set of nonterminals). b. ${\Sigma }_T$ is the terminal alphabet (set of terminal symbols), with ${\Sigma }_N\cap {\Sigma }_T=\varnothing$. c. $S\in {\Sigma }_N$ is the start symbol. d. $P$ is a finite set of production rules (or productions), where each rule is of the form $\alpha \to \beta$, with $\alpha \in ({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }{\Sigma }_N({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }$ and $\beta \in ({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }$.
2. Let $\gamma ,\delta \in ({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }$. We say $\delta$ is derivable from $\gamma$ in one step in $G$, denoted $\gamma {\Rightarrow }_G\delta$, if $\gamma ={\omega }_1\alpha {\omega }_2$ and $\delta ={\omega }_1\beta {\omega }_2$ for some rule $\alpha \to \beta \in P$ and ${\omega }_1,{\omega }_2\in ({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }$.
3. We say $\delta$ is derivable from $\gamma$ in $G$, denoted $\gamma {\Rightarrow }_G^{\ast }\delta$, if $\gamma =\delta$ or there is a sequence of one-step derivations $\gamma ={\omega }_0{\Rightarrow }_G{\omega }_1{\Rightarrow }_G\cdots {\Rightarrow }_G{\omega }_n=\delta$.
4. The language generated by $G$ is $L(G)=\{w\in {\Sigma }_T^{\ast }\mid S{\Rightarrow }_G^{\ast }w\}$.

Grammar for $L_{ge}=\{w\in \{a,b{\}}^{\ast }\mid |w{|}_a=|w{|}_b\}$

Let $G=(\{S\},\{a,b\},P,S)$ with $P=\{S\to \lambda ,S\to SS,S\to aSb,S\to bSa\}$. A derivation for baabaabb: $S\Rightarrow SS\Rightarrow SaSb\Rightarrow bSaaSb\Rightarrow baaSSb\Rightarrow baabSaSb\Rightarrow baabaSb\Rightarrow baabaaSbb\Rightarrow baabaabb$. This grammar generates all words with an equal number of ‘a’s and ‘b’s.

Grammars are inherently nondeterministic: multiple rules might apply, or multiple nonterminals could be chosen for replacement. (This flexibility allows a single grammar to describe a wide range of valid strings, reflecting the ambiguity often present in natural and programming languages.)

---

10.3 Regular Grammars and Finite Automata

The simplest type of grammars in the Chomsky Hierarchy are regular grammars.

Definition 10.2 (Chomsky Hierarchy - Part 1)

Let $G=({\Sigma }_N,{\Sigma }_T,P,S)$ be a grammar.

• $G$ is a regular grammar (Type-3 grammar) if all rules in $P$ are of the form $X\to u$ or $X\to uY$, where $X,Y\in {\Sigma }_N$ and $u\in {\Sigma }_T^{\ast }$. (These simple rules essentially allow generating a terminal symbol and then optionally transitioning to another nonterminal, mimicking the state transitions of a finite automaton.) (Typically, $u$ is restricted to a single terminal symbol or the empty string, i.e., $u\in {\Sigma }_T\cup \{\lambda \}$).

A language is regular if it is generated by a regular grammar. The class of regular languages is denoted $L_3$.

Closure Properties of Regular Languages

The class $L_3$ is closed under many operations, mirroring the closure properties of regular languages defined by finite automata.

Lemma 10.2 ( $L_3$ is closed under union)

If $L_1,L_2\in L_3$, then $L_1\cup L_2\in L_3$.

Proof of Closure under Union

Let $G_1=({\Sigma }_{N1},{\Sigma }_T,P_1,S_1)$ and $G_2=({\Sigma }_{N2},{\Sigma }_T,P_2,S_2)$ be regular grammars for $L_1$ and $L_2$, respectively. Assume ${\Sigma }_{N1}\cap {\Sigma }_{N2}=\varnothing$. Construct $G=({\Sigma }_N,{\Sigma }_T,P,S)$ where $S$ is a new start symbol, ${\Sigma }_N={\Sigma }_{N1}\cup {\Sigma }_{N2}\cup \{S\}$, and $P=P_1\cup P_2\cup \{S\to S_1,S\to S_2\}$. $G$ is regular and $L(G)=L_1\cup L_2$.

Lemma 10.3 ( $L_3$ is closed under concatenation)

If $L_1,L_2\in L_3$, then $L_1\cdot L_2\in L_3$.

Proof of Closure under Concatenation

Let $G_1=({\Sigma }_{N1},{\Sigma }_T,P_1,S_1)$ and $G_2=({\Sigma }_{N2},{\Sigma }_T,P_2,S_2)$ be regular grammars for $L_1$ and $L_2$. Assume ${\Sigma }_{N1}\cap {\Sigma }_{N2}=\varnothing$. Construct $G=({\Sigma }_N,{\Sigma }_T,P,S_1)$ where ${\Sigma }_N={\Sigma }_{N1}\cup {\Sigma }_{N2}$. $P$ contains all rules from $P_2$. For each rule $A\to w\in P_1$ (where $w\in {\Sigma }_T^{\ast }$), add $A\to w{S}_2$ to $P$. For each rule $A\to wB\in P_1$, add it to $P$. $G$ is regular and $L(G)=L_1\cdot L_2$.

Equivalence with Finite Automata

A cornerstone result is that regular grammars generate precisely the class of languages accepted by finite automata.

Theorem 10.1 (FA to Regular Grammar)

To each finite automaton $A$, there exists a regular grammar $G$ such that $L(A)=L(G)$.

Proof of FA to Regular Grammar Equivalence

Let $A=(Q,\Sigma ,\delta ,q_0,F)$ be an FA. Construct $G=(Q,\Sigma ,P,q_0)$ where:

• For each transition $\delta (p,a)=q$, add rule $p\to aq$ to $P$.
• For each accepting state $f\in F$, add rule $f\to \lambda$ to $P$. The nonterminals of $G$ are the states of $A$. A derivation in $G$ simulates a computation in $A$.

To prove the reverse, we first need to normalize regular grammars.

Definition 10.3 (Normalized Regular Grammar)

A regular grammar $G=({\Sigma }_N,{\Sigma }_T,P,S)$ is normalized if all rules are of one of the following forms:

1. $S\to \lambda$ (if $\lambda \in L(G)$)
2. $A\to a$ for $A\in {\Sigma }_N,a\in {\Sigma }_T$
3. $A\to aB$ for $A,B\in {\Sigma }_N,a\in {\Sigma }_T$

Theorem 10.2 (Normalization of Regular Grammars)

To every regular grammar, there exists an equivalent normalized regular grammar.

Proof of Normalization

The proof involves a series of transformations:

1. Eliminate chain rules ($A\to B$): For each $A$, find all $D$ such that $A{\Rightarrow }^{\ast }D$ using only chain rules. For every rule $D\to \alpha$ (where $\alpha$ is not a nonterminal), add $A\to \alpha$.
2. Eliminate $\lambda$-rules ($A\to \lambda$ for $A\ne S$): For every rule $B\to \omega A\gamma$, add $B\to \omega \gamma$.
3. Break long terminal strings: Replace $A\to a_1{a}_2\dots a_{k}B$ with $A\to a_1{X}_1,X_1\to a_2{X}_2,\dots ,X_{k-1}\to a_{k}B$ using new nonterminals. Similarly for $A\to a_1\dots a_k$.

Theorem 10.3 (Regular Grammar to NFA)

To each regular grammar $G$, there exists a nondeterministic finite automaton (NFA) $M$ such that $L(G)=L(M)$.

Proof of Regular Grammar to NFA Equivalence

Let $G=({\Sigma }_N,{\Sigma }_T,P,S)$ be a normalized regular grammar. Construct $M=({\Sigma }_N\cup \{q_F\},{\Sigma }_T,\delta ,S,F)$ where $q_F$ is a new final state.

• $F=\{q_F\}$ (and $S$ if $S\to \lambda \in P$).
• For each rule $A\to aB\in P$, add transition $\delta (A,a)=B$.
• For each rule $A\to a\in P$, add transition $\delta (A,a)=q_F$. The nonterminals of $G$ become states in $M$. A derivation in $G$ corresponds to an accepting path in $M$.

These theorems establish that regular grammars and finite automata have equivalent expressive power. (This equivalence is fundamental: it means we can either describe simple patterns using a generative grammar or recognize them using a finite-state machine, offering two complementary perspectives on the same class of languages.)

---

10.4 Context-Free Grammars and Pushdown Automata

Context-free grammars (CFGs) are more powerful than regular grammars and are fundamental to describing the syntax of programming languages.

Definition 10.2 (Chomsky Hierarchy - Part 2)

• $G$ is a context-free grammar (Type-2 grammar) if all rules in $P$ are of the form $X\to \beta$, where $X\in {\Sigma }_N$ and $\beta \in ({\Sigma }_N\cup {\Sigma }_T{)}^{\ast }$.

A language is context-free if it is generated by a context-free grammar. The class of context-free languages is denoted $L_2$. The key difference from regular grammars is that $\beta$ can contain multiple nonterminals, allowing for recursive structures. (This added flexibility allows CFGs to describe languages with nested dependencies, like correctly matched parentheses or arithmetic expressions, which regular grammars cannot handle.)

Context-Free Language $L=\{0^n{1}^n\mid n\in \mathbb{N}\}$

The grammar $G=(\{S\},\{0,1\},\{S\to \lambda ,S\to 0S1\},S)$ generates $L$. This language is not regular.

Syntax Trees

Derivations in CFGs can be represented by syntax trees (or parse trees), which visually depict the hierarchical structure of the generated word. (These trees are invaluable for understanding the structure of programming language constructs and are a core concept in compiler design.)

Definition 10.4 (Syntax Tree)

A syntax tree for a CFG $G$ is an ordered tree where:

1. The root is labeled with the start symbol.
2. Internal nodes are labeled with nonterminals.
3. Leaves are labeled with terminals or $\lambda$.
4. If an internal node labeled $A$ has children labeled ${\alpha }_1,\dots ,{\alpha }_k$ (from left to right), then $A\to {\alpha }_1\dots {\alpha }_k$ must be a production rule in $P$. The concatenation of the labels of the leaves (read from left to right) forms the generated word.

Syntax Tree for Arithmetic Expression

For the grammar $S\to S+S\mid S\ast S\mid (S)\mid \text{id}$, the expression (id * id) + id has a syntax tree showing its structure.

Normal Forms for Context-Free Grammars

For theoretical analysis and parsing algorithms, CFGs are often converted into simpler forms.

Definition 10.5 (Chomsky Normal Form and Greibach Normal Form)

Let $G=({\Sigma }_N,{\Sigma }_T,P,S)$ be a context-free grammar (where the empty string $\lambda$ is not in $L(G)$).

• $G$ is in Chomsky Normal Form (CNF) if all rules are of the form $A\to BC$ (where $A,B,C\in {\Sigma }_N$) or $A\to a$ (where $A\in {\Sigma }_N,a\in {\Sigma }_T$). (CNF ensures that every production either generates a single terminal or combines exactly two nonterminals, simplifying parsing algorithms.)
• $G$ is in Greibach Normal Form (GNF) if all rules are of the form $A\to a\alpha$ (where $A\in {\Sigma }_N,a\in {\Sigma }_T,\alpha \in {\Sigma }_N^{\ast }$). (GNF ensures that every production starts with a terminal, which is useful for top-down parsing.)

Theorem 10.4 (Existence of CNF and GNF)

For every context-free grammar $G$ with $\lambda \notin L(G)$, there exist equivalent grammars in Chomsky Normal Form and in Greibach Normal Form.

Proof of Existence of CNF and GNF

The conversion to CNF typically involves:

1. Eliminating useless symbols (nonterminals that cannot be reached or cannot derive a terminal string).
2. Eliminating $\lambda$-productions (rules $A\to \lambda$, except $S\to \lambda$).
3. Eliminating chain rules ($A\to B$).
4. Replacing rules with mixed terminals/nonterminals or long right-hand sides with new nonterminals and binary rules.

Pumping Lemma for Context-Free Languages

Similar to regular languages, there’s a pumping lemma for CFGs to prove that a language is not context-free.

Lemma 10.6 (Pumping Lemma for Context-Free Languages)

If $L$ is a context-free language, then there exists a constant $n_L$ (depending only on $L$) such that for all words $z\in L$ with $|z|\ge n_L$, there exists a decomposition $z=uvwxy$ such that:

1. $|vx|\ge 1$ (at least one of $v$ or $x$ is non-empty).
2. $|vwx|\le n_L$.
3. $u{v}^{i}w{x}^{i}y\in L$ for all $i\in \mathbb{N}$.

(Important Note: The Pumping Lemma can only be used to prove that a language is not context-free. It cannot be used to prove that a language is context-free.)

Proof of Pumping Lemma for CFLs

The proof relies on the fact that in any sufficiently long derivation tree, some nonterminal must repeat on a path from the root to a leaf. This repeating nonterminal allows for “pumping” (repeating or removing) the corresponding segments of the word.

Proving $L=\{a^n{b}^n{c}^n\mid n\in \mathbb{N}\}$ is not context-free

Assume $L$ is context-free. Let $n_L$ be the pumping length. Choose $z=a^{n_L}{b}^{n_L}{c}^{n_L}\in L$. By the pumping lemma, $z=uvwxy$ with $|vx|\ge 1$ and $|vwx|\le n_L$. Since $|vwx|\le n_L$, the segment $vwx$ cannot contain all three types of symbols ($a,b,c$). It can contain at most two types. If $vwx$ contains only $a$‘s and $b$‘s (or only $b$‘s and $c$‘s, or only $a$‘s), then pumping $v$ and $x$ (i.e., forming $u{v}^{2}w{x}^{2}y$) will increase the count of only one or two types of symbols, while the third remains unchanged. This breaks the $a^n{b}^n{c}^n$ pattern, so $u{v}^{2}w{x}^{2}y\notin L$. This contradicts condition (3) of the pumping lemma, so $L$ is not context-free.

Pushdown Automata

Nondeterministic Pushdown Automata (NPdAs) are the machine model equivalent to context-free grammars. They extend finite automata with a stack (a LIFO data structure) for memory. (This stack memory is crucial for handling nested structures, like matching parentheses, which finite automata cannot do.)

Definition 10.6 (Nondeterministic Pushdown Automaton)

An NPdA is a 6-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0)$, where:

• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet.
• $\Gamma$ is the stack alphabet.
• $\delta$ is the transition function: $Q\times (\Sigma \cup \{\lambda \})\times \Gamma \to \mathcal{P}(Q\times {\Gamma }^{\ast })$.
• $q_0\in Q$ is the initial state.
• $Z_0\in \Gamma$ is the initial stack symbol. An NPdA accepts a word $w$ if, starting in $q_0$ with $Z_0$ on the stack, it can read $w$ and empty its stack.

NPdA for $L=\{0^n{1}^n\mid n\in \mathbb{N}\}$

An NPdA for $L$ would push a ‘0’ onto the stack for each ‘0’ read from the input. When a ‘1’ is read, it pops a ‘0’ from the stack. If the stack is empty when all ‘1’s are read, the word is accepted.

Equivalence of CFGs and NPdAs

A language $L$ is context-free if and only if there exists a nondeterministic pushdown automaton $M$ such that $L=L(M)$.

Proof of Equivalence of CFGs and NPdAs

• CFG to NPdA: Given a CFG in Greibach Normal Form, an NPdA can be constructed with a single state. For a rule $A\to a\alpha$, the NPdA reads $a$, pops $A$ from the stack, and pushes ${\alpha }^R$ (reversed $\alpha$).
• NPdA to CFG: This is more complex. It involves constructing a CFG whose nonterminals represent the state changes and stack contents of the NPdA.

---

10.5 Context-Sensitive and Unrestricted Grammars

Beyond context-free grammars lie more powerful types, completing the Chomsky Hierarchy.

Definition 10.2 (Chomsky Hierarchy - Part 3)

• $G$ is a context-sensitive grammar (Type-1 grammar) if all rules $\alpha \to \beta \in P$ satisfy $|\alpha |\le |\beta |$, and $\alpha$ contains at least one nonterminal. (This means a nonterminal can only be replaced if it’s in a specific “context” of surrounding symbols, and the replacement cannot make the string shorter.) (The restriction $|\alpha |\le |\beta |$ means rules cannot shorten strings).
• $G$ is an unrestricted grammar (Type-0 grammar) if it has no restrictions on its rules other than $\alpha$ containing at least one nonterminal.

A language is context-sensitive (resp. recursively enumerable) if it is generated by a context-sensitive (resp. unrestricted) grammar. The classes are denoted $L_1$ and $L_0$.

Generative Power and Automata Equivalence

• Context-Sensitive Grammars ($L_1$): These grammars can model languages where the replacement of a nonterminal depends on its surrounding context. They are equivalent in power to Linear Bounded Automata (LBAs), which are Turing machines whose tape head cannot move beyond the portion of the tape initially occupied by the input. Context-sensitive languages are decidable.
• Unrestricted Grammars ($L_0$): These are the most powerful grammars, equivalent to Turing Machines. They can generate any recursively enumerable language. Languages generated by unrestricted grammars are not necessarily decidable.

The Chomsky Hierarchy forms a strict inclusion: $L_3\subset L_2\subset L_1\subset L_0$. (This means each level of the hierarchy is strictly more powerful than the one below it; there are languages that can be generated by a Type-X grammar but not by a Type-(X+1) grammar.)

---

Summary

• Grammars are generative models for languages, defined by nonterminals, terminals, production rules, and a start symbol.
• The Chomsky Hierarchy classifies grammars into four types based on restrictions on their production rules, each corresponding to a different class of languages and computational power.
  • Type-3 (Regular Grammars): Generate regular languages, equivalent to finite automata. Rules are $X\to u$ or $X\to uY$.
  • Type-2 (Context-Free Grammars): Generate context-free languages, equivalent to pushdown automata. Rules are $X\to \beta$. Crucial for programming language syntax.
  • Type-1 (Context-Sensitive Grammars): Generate context-sensitive languages, equivalent to linear bounded automata. Rules $\alpha \to \beta$ with $|\alpha |\le |\beta |$.
  • Type-0 (Unrestricted Grammars): Generate recursively enumerable languages, equivalent to Turing machines. No restrictions on rules.
• Syntax trees provide a hierarchical representation of derivations in context-free grammars.
• Normal forms (Chomsky Normal Form, Greibach Normal Form) simplify CFGs for analysis and parsing.
• Pumping lemmas (for regular and context-free languages) are powerful tools for proving that a language does not belong to a particular class.
• The hierarchy demonstrates a fundamental trade-off between the expressiveness of a language model and the complexity of the automaton required to process it.

---

Previous Chapter: Chapter 9 - Communication and Cryptography

Exercises

Exercise 10.1 (Regular Grammar Construction)

Construct a regular grammar for the language $L=\{w\in \{0,1{\}}^{\ast }\mid |w{|}_0\text{ is even}\}$.

Solution

Let $G=(\{S_0,S_1\},\{0,1\},P,S_0)$, where $S_0$ means an even number of 0s seen, and $S_1$ means an odd number of 0s seen. $P=\{S_0\to 1S_0,S_0\to 0S_1,S_0\to \lambda ,S_1\to 1S_1,S_1\to 0S_0\}$.

Exercise 10.2 (Context-Free Grammar for Palindromes)

Construct a context-free grammar for the language of palindromes over {a, b}, i.e., $L=\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$.

Solution

$G=(\{S\},\{a,b\},P,S)$ with $P=\{S\to \lambda ,S\to aSa,S\to bSb,S\to a,S\to b\}$. (Note: $S\to a$ and $S\to b$ are for odd-length palindromes).

Exercise 10.3 (Pumping Lemma for Context-Free Languages)

Prove that the language $L=\{a^n{b}^n{c}^n{d}^n\mid n\in \mathbb{N}\}$ is not context-free using the Pumping Lemma for Context-Free Languages.

Solution

Assume $L$ is context-free. Let $n_L$ be the pumping length. Choose $z=a^{n_L}{b}^{n_L}{c}^{n_L}{d}^{n_L}\in L$. By the pumping lemma, $z=uvwxy$ with $|vx|\ge 1$ and $|vwx|\le n_L$. Since $|vwx|\le n_L$, the segment $vwx$ can span at most three of the four blocks of identical symbols.

Case 1: $vwx$ contains symbols from only one block (e.g., only $a$‘s). Pumping $v$ and $x$ (i.e., $u{v}^{2}w{x}^{2}y$) will increase the count of only $a$‘s, breaking the $a^n{b}^n{c}^n{d}^n$ pattern. Case 2: $vwx$ contains symbols from two adjacent blocks (e.g., $a$‘s and $b$‘s). Pumping will increase the count of $a$‘s and $b$‘s, but not $c$‘s or $d$‘s, breaking the pattern. Case 3: $vwx$ contains symbols from two non-adjacent blocks (e.g., $a$‘s and $c$‘s). This is impossible since $vwx$ is a contiguous substring and $|vwx|\le n_L$.

In all valid cases, pumping $v$ and $x$ leads to a string not in $L$, contradicting the pumping lemma. Therefore, $L$ is not context-free.

Exercise 10.4 (Pushdown Automaton Design)

Design a nondeterministic pushdown automaton (NPdA) for the language $L=\{w\in \{a,b{\}}^{\ast }\mid w\text{ has an equal number of }a\text{’s and }b\text{’s}\}$.

Solution

This is a classic example where an NPdA can be designed. The NPdA would use its stack to keep track of the imbalance between ‘a’s and ‘b’s. Let $M=(\{q_0\},\{a,b\},\{A,B,Z_0\},\delta ,q_0,Z_0)$.

• If an ‘a’ is read: If ‘B’ is on top of stack, pop ‘B’. Else, push ‘A’.
• If a ‘b’ is read: If ‘A’ is on top of stack, pop ‘A’. Else, push ‘B’.
• Accept if stack is empty (only $Z_0$ remains) after reading the entire input.

This requires a bit more detail in the transition function $\delta$ to handle $Z_0$ and ensure correct pushing/popping. For example:

• $\delta (q_0,a,Z_0)=\{(q_0,A{Z}_0)\}$
• $\delta (q_0,b,Z_0)=\{(q_0,B{Z}_0)\}$
• $\delta (q_0,a,A)=\{(q_0,AA)\}$
• $\delta (q_0,b,B)=\{(q_0,BB)\}$
• $\delta (q_0,a,B)=\{(q_0,\lambda )\}$
• $\delta (q_0,b,A)=\{(q_0,\lambda )\}$
• $\delta (q_0,\lambda ,Z_0)=\{(q_0,\lambda )\}$ (for acceptance if stack is empty)

This NPdA accepts the language.