Pushdown Automata (PDA)

Contents

11. Pushdown Automata (PDA)#

Introduction#

A Pushdown Automaton (PDA) is a a type of computational model that extends finite automata with a stack as auxiliary memory. PDAs are used to recognize context-free languages, making them more powerful than finite automata but less powerful than Turing machines.

1. Key Components of a PDA:#

A PDA is a collection of following key components:

  • Input alphabet (Σ): The set of all possible input symbols that can appear in the input string

  • Stack alphabet (Γ): The set of all symbols that can be stored on the stack

  • Input tape: Contains the input string to be processed

  • Pushdown stack: Last-In-First-Out (LIFO) data structure that can grow infinitely tall with PUSH and POP operations

  • Finite set of states (Q), including:

    • Start state (q₀): Initial state of the PDA

    • Accept states: States that lead to acceptance

    • Reject states: States that lead to rejection

    • Push states: States where stack PUSH operations occur

    • Pop states: States where stack POP operations occur

    • Read states: States where input symbols are read from the input tape

  • Transition functions (δ): Maps current configuration to next configuration, Format: \(δ(q, a, X) = (p, γ)\) where:

    • q = current state

    • a = input symbol (or ∧ for empty string)

    • X = top stack symbol

    • p = next state

    • γ = string of stack symbols to replace X

  • Initial stack symbol (Z₀): Special symbol marking bottom of stack, usually the blank symbol (Δ)

2. Example Python Implementation: General PDA Simulator#

The PushdownAutomaton class below implements the formal definition from Section 1. Before reading the code, map each constructor parameter to its formal counterpart:

Constructor parameter

Formal component

Section 1 notation

states

Finite set of states

Q

input_alphabet

Input alphabet

Σ

stack_alphabet

Stack alphabet

Γ

transitions

Transition function

δ

initial_state

Start state

q₀

initial_stack_symbol

Bottom-of-stack marker

Z₀ (shown as Δ)

accepting_states

Accept states

F

How transitions are encoded: The transitions dictionary uses the key (state, input_symbol, stack_top) and the value (new_state, new_stack_symbols). This directly mirrors the formal notation δ(q, a, X) = (p, γ) from Section 1:

δ(q,    a,            X)         = (p,          γ               )
  state  input_symbol  stack_top    new_state    new_stack_symbols

When input_symbol == '' (empty string), the transition is an ε-transition (also written ∧ in the textbook) — it fires without consuming any input symbol.

Two-phase processing loop: The process_input method alternates between:

  1. Consuming one input symbol and applying the matching transition

  2. Exhausting any ε-transitions that become available after that step

This matches the formal definition of a PDA configuration: at each step, the machine may optionally take ε-transitions before reading the next symbol.

Outside Jupyter: Copy this class into pda_simulator.py and run with:

python pda_simulator.py

No external packages are needed — this class uses only the Python standard library.

# ─────────────────────────────────────────────────────────────────────────────
# General Pushdown Automaton Simulator
#
# Implements the formal PDA definition from Section 1:
#   δ(q, a, X) = (p, γ)
#   where q = current state, a = input symbol ('' for ε), X = stack top,
#         p = next state, γ = replacement string pushed onto stack
#
# Running outside Jupyter:
#   python pda_simulator.py
# ─────────────────────────────────────────────────────────────────────────────


class PushdownAutomaton:
    """
    Simulates a nondeterministic Pushdown Automaton (PDA).

    Transition table format:
        { (state, input_sym, stack_top): (new_state, [symbols_to_push]) }

    Use input_sym = '' for ε-transitions (no input consumed).
    new_stack_symbols = [] means POP only (replace stack_top with nothing).
    """

    def __init__(self, states, input_alphabet, stack_alphabet,
                 transitions, initial_state, initial_stack_symbol,
                 accepting_states):
        self.states               = states
        self.input_alphabet       = input_alphabet
        self.stack_alphabet       = stack_alphabet
        self.transitions          = transitions          # δ: (q, a, X) → (p, γ)
        self.initial_state        = initial_state        # q₀
        self.initial_stack_symbol = initial_stack_symbol # Z₀ (typically Δ)
        self.accepting_states     = accepting_states     # F

        # Reset stack and state for each new run (see process_input)
        self.stack         = [initial_stack_symbol]
        self.current_state = initial_state

    def try_epsilon_transitions(self, current_state, stack):
        """
        Apply ε-transitions (input_sym == '') greedily until none remain.

        ε-transitions fire without consuming input — they correspond to
        the ∧ symbol in δ(q, ∧, X) = (p, γ) from Section 1.
        We keep looping because one ε-transition may enable another.
        """
        while True:
            epsilon_found = False
            for (state, input_sym, stack_top), (new_state, new_stack_syms) \
                    in self.transitions.items():

                # Match: correct state, ε-transition, correct stack top
                if (state == current_state and input_sym == '' and
                        stack and stack[-1] == stack_top):

                    # Apply the transition: pop stack_top, push new symbols
                    current_state = new_state
                    stack.pop()                            # POP X
                    for s in reversed(new_stack_syms):    # PUSH γ in LIFO order
                        stack.append(s)
                    epsilon_found = True
                    print(f"ε-transition: State = {current_state}, Stack = {stack}")
                    break  # restart scan after any change

            if not epsilon_found:
                break  # fixed point: no more ε-transitions available

        return current_state, stack

    def process_input(self, input_string):
        """
        Simulate the PDA on input_string.

        Processing loop (Section 1 configuration semantics):
          1. Apply any available ε-transitions.
          2. Read the next input symbol a.
          3. Find a transition δ(current_state, a, stack_top) = (p, γ).
          4. Apply it: pop stack_top, push γ, advance to state p.
          5. Apply any ε-transitions that became available.
          6. Repeat until input is exhausted.
          7. Accept iff current_state ∈ F (accepting_states).

        Returns True if the string is accepted, False otherwise.
        """
        current_state = self.initial_state
        stack         = [self.initial_stack_symbol]  # stack initialized to [Z₀]

        print(f"Starting configuration: State = {current_state}, Stack = {stack}")

        # Phase 0: fire any ε-transitions before reading any input
        current_state, stack = self.try_epsilon_transitions(current_state, stack)

        i = 0
        while i < len(input_string):
            symbol = input_string[i]

            if symbol not in self.input_alphabet:
                raise ValueError(f"Symbol '{symbol}' not in input alphabet Σ")

            # Search for a valid transition δ(current_state, symbol, stack_top)
            transition_found = False
            for (state, input_sym, stack_top), (new_state, new_stack_syms) \
                    in self.transitions.items():

                if (state == current_state and input_sym == symbol and
                        stack and stack[-1] == stack_top):

                    # Apply δ(q, a, X) = (p, γ):
                    current_state = new_state
                    stack.pop()                            # POP X (the old stack top)
                    for s in reversed(new_stack_syms):    # PUSH γ in LIFO order
                        stack.append(s)
                    transition_found = True
                    print(f"Read '{symbol}': State = {current_state}, Stack = {stack}")

                    # Fire any ε-transitions enabled by this new configuration
                    current_state, stack = self.try_epsilon_transitions(
                        current_state, stack)
                    break

            if not transition_found:
                # No valid transition → PDA blocks → implicit rejection
                print(f"No transition for ('{current_state}', '{symbol}', "
                      f"'{stack[-1] if stack else 'empty'}'): PDA blocks → REJECT")
                return False

            i += 1

        # After all input consumed: fire final ε-transitions
        current_state, stack = self.try_epsilon_transitions(current_state, stack)

        # Accept iff we are in an accepting state (stack contents don't matter
        # for acceptance-by-state; for acceptance-by-empty-stack, check stack == [])
        accepted = current_state in self.accepting_states
        print(f"Final state: {current_state} → {'ACCEPT' if accepted else 'REJECT'}")
        return accepted

3. Examples of PDAs#

3.1 Example 1: PDA for {\(a^nb^n\) where \(n = 0, 1, 2, \dots\)}#

3.1.1 Visual Representation of the PDA#

Below is a diagram representing a PDA that acceptes the langauge {\(a^nb^n\) where \(n = 0, 1, 2, \dots\)}. The diagram uses:

  • Diamonds (♢) for READ and POP operations

  • Rectangles (□) for PUSH operations

  • Rounded rectangles for START/ACCEPT/REJECT states

  • Δ represents blank or empty symbol

  • Arrows show transitions between states

        flowchart TD
    accTitle: Example 1 PDA
    accDescr: a  diagram representing a PDA that acceptes the langauge {$a^nb^n$ where $n = 0, 1, 2, \dots$}
    START([START]) --> READ1{READ}
    READ1 -->|a| PUSH[PUSH a]
    PUSH --> READ1
    READ1 -->|Δ| POP2{POP}
    READ1 -->|b| POP1{POP}
    POP1 -->|b, Δ| REJECT1([REJECT])
    POP1 -->|a| READ2{READ}
    READ2 -->|a| REJECT2([REJECT])
    READ2 -->|b| POP1
    READ2 -->|Δ| READ1
    POP2 -->|Δ| ACCEPT([ACCEPT])
    POP2 -->|a, b| REJECT3([REJECT])

3.1.2 Key Components of this specific PDA#

  • Input Alphabet (Σ): Σ = {a, b}. The PDA processes strings containing only ‘a’ and ‘b’ symbols

  • Stack Alphabet (Γ): Γ = {a, Δ}. Only ‘a’ is explicitly pushed onto the stack. Δ (blank symbol) is implicitly present as the initial stack symbol

  • States (Q):

    • Start state: Initial state where computation begins

    • Read states: Two diamond-shaped READ nodes that process input symbols and make branching decisions based on the symbols read from the input tape

    • Push state: One rectangular PUSH node that adds ‘a’ to stack

    • Pop states: Two diamond-shaped POP nodes that remove symbols from top of the stack and make branching decisions based on the symbols popped from the stack

    • Accept state: One terminal state for successful computations

    • Reject states: Three terminal states for invalid inputs/configurations

  • Transitions (δ):

    • From START: Transitions to first READ state

    • From first READ state:

      • On input ‘a’: Transitions to PUSH state

      • On input ‘b’: Transitions to first POP state

      • On empty input (Δ): Transitions to second POP state

    • From PUSH state: After pushing ‘a’: Returns to first READ state

    • From first POP state:

      • On stack symbol ‘b’ or empty stack (Δ): Transitions to REJECT

      • On stack symbol ‘a’: Transitions to second READ state

    • From second READ state:

      • On input ‘a’: Transitions to REJECT

      • On input ‘b’: Transitions to first POP state

      • On empty input (Δ): Transitions to first READ state

    • From second POP state:

      • On empty input (Δ): Transitions to ACCEPT

      • On inputs ‘a’ or ‘b’: Transitions to REJECT

  • Transition Labels: The labels on the arrows represent different conditions:

    • For transitions from READ states (e.g., “a”, “b”, “Δ”): These represent the input symbol being read from the input tape. “Δ” specifically represents empty input (end of input string)

    • For transitions from POP states (e.g., “b, Δ”, “a, b”): These represent the symbol at the top of the stack. When multiple symbols are listed (e.g., “a, b”), the transition applies for either symbol. “Δ” here represents a blank symbol or an empty stack. For example, “b, Δ” means “take this transition if either ‘b’ is on top of stack OR stack is empty”.

3.1.3 Processing Example: Input String “aabb”#

Let’s track how the PDA processes the input string “aabb”. Each state shows the remaining input and current stack content.

        flowchart TD
    accTitle: Processing Example
    accDescr: a diagram representing how the PDA processes the input string "aabb"
    subgraph Step1["Step 1: Read 'a'"]
        direction TB
        s1[Input: aabb] --> s1t["Stack: Δ"]
        s1c["Current State: READ"]
    end
    subgraph Step2["Step 2: Push 'a'"]
        direction TB
        s2[Input: abb] --> s2t["Stack: a,Δ"]
        s2c["Current State: PUSH"]
    end
    subgraph Step3["Step 3: Read 'a'"]
        direction TB
        s3[Input: abb] --> s3t["Stack: a,Δ"]
        s3c["Current State: READ"]
    end
    subgraph Step4["Step 4: Push 'a'"]
        direction TB
        s4[Input: bb] --> s4t["Stack: a,a,Δ"]
        s4c["Current State: PUSH"]
    end
    subgraph Step5["Step 5: Read 'b'"]
        direction TB
        s5[Input: bb] --> s5t["Stack: a,a,Δ"]
        s5c["Current State: READ"]
    end
    subgraph Step6["Step 6: Pop 'a'"]
        direction TB
        s6[Input: b] --> s6t["Stack: a,Δ"]
        s6c["Current State: POP"]
    end
    subgraph Step7["Step 7: Read 'b'"]
        direction TB
        s7[Input: b] --> s7t["Stack: a,Δ"]
        s7c["Current State: READ"]
    end
    subgraph Step8["Step 8: Pop 'a'"]
        direction TB
        s8[Input: Δ] --> s8t["Stack: Δ"]
        s8c["Current State: POP"]
    end
    subgraph Step9["Step 9: Final"]
        direction TB
        s9[Input: Δ] --> s9t["Stack: Δ"]
        s9c["Current State: ACCEPT"]
    end

    Step1 --> Step2
    Step2 --> Step3
    Step3 --> Step4
    Step4 --> Step5
    Step5 --> Step6
    Step6 --> Step7
    Step7 --> Step8
    Step8 --> Step9

3.1.4 Understanding the READ State and Input Tape#

The input tape contains cells, where each cell holds one symbol. The tape is read from left to right, and a read head points to the current cell being processed.

How READ State Works:

  • The read head points to the current symbol being processed

  • When a symbol is read, the head moves one position to the right

  • The READ state makes decisions based on the current symbol

  • The tape cells extend as needed, always ending with Δ

3.1.5 Code Example: Visualizing the Input Tape#

The PDA diagram in Section 3.1.1 and the step-by-step trace in Section 3.1.3 described what the PDA does at each step. This code makes that concrete by rendering the input tape as an ASCII box diagram and showing the read head position with an arrow (↑).

Two helper functions:

Function

Purpose

print_tape(tape, head_position)

Draws the tape and positions the ↑ read head

visualize_pda_step(step_num, tape, head_pos, current_symbol, action)

Wraps print_tape with step number, current symbol, and action label

What each argument represents:

tape            → list of symbol strings, ending with 'Δ' (end-of-input marker)
head_position   → index into tape; 0 = leftmost cell (matches left-to-right reading)
current_symbol  → the symbol at tape[head_position] (redundant but clarifying)
action          → plain-English description of the PDA's response (PUSH/POP/REJECT)

The five visualize_pda_step calls below trace the processing of "aabb" from Section 3.1.3. The stack is not shown here because the aⁿbⁿ example focuses on tape mechanics; Section 3.2.4 adds a stack column for the PalindromeX example where stack contents are the key insight.

Outside Jupyter: Both functions use only print() — no special packages needed. Run the complete cell with python tape_visualizer.py.

# ─────────────────────────────────────────────────────────────────────────────
# Tape Visualizer — aⁿbⁿ PDA (Section 3.1.3)
#
# Renders the input tape and read-head position at each PDA step.
# Traces the processing of "aabb" to match Section 3.1.3 exactly.
#
# Running outside Jupyter:
#   python tape_visualizer.py
# ─────────────────────────────────────────────────────────────────────────────


def print_tape(tape, head_position):
    """
    Draw the input tape as an ASCII box and place the ↑ read head below it.

    Args:
        tape          (list[str]): Symbols on the tape, last cell is 'Δ'.
        head_position (int):       Index of the cell currently being read.
    """
    n = len(tape)

    # Top border: ┌───┬───┬ ... ───┐
    print('┌' + '───┬' * (n - 1) + '───┐')

    # Cell row: │ a │ b │ ...
    print('│', end=' ')
    for symbol in tape:
        print(f'{symbol} │', end=' ')
    print()

    # Bottom border: └───┴───┴ ... ───┘
    print('└' + '───┴' * (n - 1) + '───┘')

    # Read-head row: one '↑ ' under the current cell, spaces elsewhere
    # Each cell is 4 characters wide (e.g., '│ a │'), so spacing is 4 chars
    print(' ', end='')
    for i in range(n):
        print('↑ ' if i == head_position else '    ', end='')
    print('\n')


def visualize_pda_step(step_num, tape, head_pos, current_symbol, action):
    """
    Print a complete PDA step: step number, tape with read head, and action.

    Args:
        step_num       (int):       Step counter for display.
        tape           (list[str]): Full tape contents.
        head_pos       (int):       Current read-head index.
        current_symbol (str):       Symbol at tape[head_pos] (shown for clarity).
        action         (str):       Description of what the PDA does next.
    """
    print(f"### Step {step_num}:")
    print_tape(tape, head_pos)
    print(f"Current Symbol: {current_symbol}")
    print(f"Action: {action}\n")


# ── Trace: processing "aabb" (Section 3.1.3) ──────────────────────────────────
# The tape is fixed throughout; only the read head (head_pos) advances.
# 'Δ' in the last cell represents end-of-input (Section 1: Z₀ / blank symbol).

tape = ['a', 'a', 'b', 'b', 'Δ']

# Step 1: head at index 0, reads 'a' → transition to PUSH state
visualize_pda_step(1, tape, 0, 'a', "Read 'a': transition to PUSH state, push 'a' onto stack")

# Step 2: head at index 1, reads second 'a' → PUSH again
visualize_pda_step(2, tape, 1, 'a', "Read 'a': transition to PUSH state, push 'a' onto stack")

# Step 3: head at index 2, reads first 'b' → switch to POP state
# Stack now has [a, a, Δ]; reading 'b' means we have seen all a's
visualize_pda_step(3, tape, 2, 'b', "Read 'b': transition to POP state, pop 'a' from stack")

# Step 4: head at index 3, reads second 'b' → POP again
# Stack now has [a, Δ]; each 'b' must match one 'a' pushed earlier
visualize_pda_step(4, tape, 3, 'b', "Read 'b': transition to POP state, pop 'a' from stack")

# Step 5: head at index 4, reads 'Δ' → end of input
# Stack should now contain only [Δ] → transition to ACCEPT
visualize_pda_step(5, tape, 4, 'Δ', "End of input (Δ): stack contains only Δ → ACCEPT")

### Step 1:
┌───┬───┬───┬───┬───┐
│ a │ a │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┘
 ↑                 

Current Symbol: a
Action: Read 'a': transition to PUSH state, push 'a' onto stack

### Step 2:
┌───┬───┬───┬───┬───┐
│ a │ a │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┘
     ↑             

Current Symbol: a
Action: Read 'a': transition to PUSH state, push 'a' onto stack

### Step 3:
┌───┬───┬───┬───┬───┐
│ a │ a │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┘
         ↑         

Current Symbol: b
Action: Read 'b': transition to POP state, pop 'a' from stack

### Step 4:
┌───┬───┬───┬───┬───┐
│ a │ a │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┘
             ↑     

Current Symbol: b
Action: Read 'b': transition to POP state, pop 'a' from stack

### Step 5:
┌───┬───┬───┬───┬───┐
│ a │ a │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┘
                 ↑ 

Current Symbol: Δ
Action: End of input (Δ): stack contains only Δ → ACCEPT

3.2 Example 2: PDA for PalindromeX#

3.2.1 Visual Representation of the PDA#

Below is a diagram representing a PDA that acceptes the langauge PalindromeX which consists of all words in the form \(\{sX\text{reverse}(s)\}\) where s is any string over the given alphabet.

        flowchart TD
    accTitle: Visual Representation of the PDA
    accDescr: a diagram representing a PDA that acceptes the langauge PalindromeX
    START([START]) --> READ1{READ}
    READ1 -->|a| PUSH_A[PUSH a]
    READ1 -->|b| PUSH_B[PUSH b]
    PUSH_A --> READ1
    PUSH_B --> READ1
    READ1 -->|X| READ2{READ}
    READ2 -->|a| POP1{POP}
    READ2 -->|b| POP2{POP}
    READ2 -->|Δ| POP3{POP}
    POP1 -->|a| READ2
    POP2 -->|b| READ2
    POP3 -->|Δ| ACCEPT([ACCEPT])

3.2.2 Key Components of this PDA#

  • Input Alphabet (Σ): Σ = {a, b, X}, where X serves as a middle marker

  • Stack Alphabet (Γ): Γ = {a, b, Δ} where Δ is the blank symbol

  • States (Q):

    • Start state: Initial configuration

    • READ states: Two read states before and after X

    • PUSH states: For pushing ‘a’ and ‘b’ onto stack

    • POP states: For matching and removing symbols from stack

    • Accept state: Final accepting configuration

  • Key Features:

    • Before X: Pushes symbols onto stack

    • After X: Pops and matches symbols in reverse order

    • Accepts when stack is empty (except Δ) and input is fully processed

3.2.3 Processing Example: Input String “abXba”#

Let’s track the processing of input string “abXba” step by step:

  • Initial Phase (Before X):

    • Read ‘a’: Push ‘a’ onto stack

    • Read ‘b’: Push ‘b’ onto stack

    • Stack becomes [b, a, Δ] (top to bottom)

  • Middle Marker:

    • Read ‘X’: Transition to second READ state

    • Stack remains [b, a, Δ]

  • Matching Phase (After X):

    • Read ‘b’: Matches and pops ‘b’ from stack

    • Read ‘a’: Matches and pops ‘a’ from stack

    • Stack becomes [Δ]

  • Acceptance:

    • Input is empty

    • Stack contains only Δ

    • PDA moves to ACCEPT state

3.2.4 Code Example: Visualizing Tape and Stack Together#

The PalindromeX PDA (Section 3.2.1) is more complex than the aⁿbⁿ PDA because the stack contents are the central insight: the first half of the string (before X) is pushed symbol by symbol, then the second half (after X) must pop each symbol in reverse order. If the stack is empty exactly when the input ends, the string is accepted.

This cell redefines visualize_pda_step to show both the tape and the stack at every step. The new signature adds two parameters:

visualize_pda_step(step_num, tape, head_pos, stack_contents, state, action)
                                             ^^^^^^^^^^^^^^  ^^^^^
                                             NEW: stack list  NEW: PDA state name

Reading the stack display: The stack is printed top-to-bottom (top = most recently pushed = next to be popped). ‘Δ’ at the bottom always represents the initial stack symbol Z₀ — it can never be popped in normal operation.

What the six steps show: The six visualize_pda_step calls trace "abXba" from Section 3.2.3:

Step

Phase

Symbol

Stack change

1

Push phase

‘a’

Push ‘a’ → [a, Δ]

2

Push phase

‘b’

Push ‘b’ → [b, a, Δ]

3

Marker

‘X’

No change → [b, a, Δ]

4

Match phase

‘b’

Pop ‘b’ → [a, Δ]

5

Match phase

‘a’

Pop ‘a’ → [Δ]

6

Accept

‘Δ’

Only Δ remains → ACCEPT

Outside Jupyter: Run with python palindrome_visualizer.py.

# ─────────────────────────────────────────────────────────────────────────────
# Tape + Stack Visualizer — PalindromeX PDA (Section 3.2.3)
#
# Redefines visualize_pda_step to show both the tape and stack at each step.
# Traces acceptance of "abXba" to match Section 3.2.3 exactly.
#
# Running outside Jupyter:
#   python palindrome_visualizer.py
# ─────────────────────────────────────────────────────────────────────────────


def visualize_pda_step(step_num, tape, head_pos, stack_contents, state, action):
    """
    Display one PDA step with both tape (read head) and stack (top-to-bottom).

    Args:
        step_num       (int):       Step counter.
        tape           (list[str]): Full tape, last cell is 'Δ'.
        head_pos       (int):       Current read-head index.
        stack_contents (list[str]): Stack from top to bottom (top = index 0).
        state          (str):       Current PDA state name (e.g., 'READ', 'POP').
        action         (str):       What the PDA does at this step.
    """
    print(f"Step {step_num}:")

    # ── Tape with read head ───────────────────────────────────────────────────
    n = len(tape)
    print("Tape:")
    print('┌' + '───┬' * (n - 1) + '───┐')
    print('│', end=' ')
    for symbol in tape:
        print(f'{symbol} │', end=' ')
    print()
    print('└' + '───┴' * (n - 1) + '───┘')
    print(' ', end='')
    for i in range(n):
        print('↑ ' if i == head_pos else '    ', end='')
    print('\n')

    # ── Stack (top to bottom) ─────────────────────────────────────────────────
    # Showing top-to-bottom matches LIFO intuition: the top is the next to be popped.
    print("Stack (top to bottom):")
    print('┌───┐')
    for symbol in stack_contents:
        print(f'│ {symbol} │')   # each row is one stack symbol
    print('└───┘\n')

    print(f"Current State: {state}")
    print(f"Action: {action}\n")


# ── Trace: "abXba" accepted (Section 3.2.3) ───────────────────────────────────
# Phase 1 (before X): push each input symbol onto the stack.
# Phase 2 (after X):  pop and match each symbol against the reversed prefix.
# Acceptance: stack contains only Δ when input is exhausted.

tape = ['a', 'b', 'X', 'b', 'a', 'Δ']

# Step 1: read 'a' → push 'a'; stack grows to [a, Δ]
visualize_pda_step(1, tape, 0, ['Δ'],
                   'READ',
                   "Read 'a': move to PUSH-a state, push 'a' onto stack → stack becomes [a, Δ]")

# Step 2: read 'b' → push 'b'; stack grows to [b, a, Δ]
visualize_pda_step(2, tape, 1, ['a', 'Δ'],
                   'READ',
                   "Read 'b': move to PUSH-b state, push 'b' onto stack → stack becomes [b, a, Δ]")

# Step 3: read 'X' (middle marker) → no stack change; switch to matching phase
visualize_pda_step(3, tape, 2, ['b', 'a', 'Δ'],
                   'READ',
                   "Read 'X': middle marker — switch to second READ state, no stack change")

# Step 4: read 'b' → pop 'b' from stack (matches top); stack becomes [a, Δ]
# This is the first match: the symbol after X must equal the symbol pushed last
visualize_pda_step(4, tape, 3, ['b', 'a', 'Δ'],
                   'READ',
                   "Read 'b': matches top of stack 'b' → POP, stack becomes [a, Δ]")

# Step 5: read 'a' → pop 'a' from stack (matches); stack becomes [Δ]
visualize_pda_step(5, tape, 4, ['a', 'Δ'],
                   'READ',
                   "Read 'a': matches top of stack 'a' → POP, stack becomes [Δ]")

# Step 6: end of input ('Δ'); stack contains only Δ → ACCEPT
# The stack being reduced to just Δ (Z₀) confirms every pushed symbol was matched
visualize_pda_step(6, tape, 5, ['Δ'],
                   'POP',
                   "End of input; stack contains only Δ (Z₀) → move to ACCEPT state")

Step 1:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
 ↑                     

Stack (top to bottom):
┌───┐
│ Δ │
└───┘

Current State: READ
Action: Read 'a': move to PUSH-a state, push 'a' onto stack → stack becomes [a, Δ]

Step 2:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
     ↑                 

Stack (top to bottom):
┌───┐
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'b': move to PUSH-b state, push 'b' onto stack → stack becomes [b, a, Δ]

Step 3:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
         ↑             

Stack (top to bottom):
┌───┐
│ b │
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'X': middle marker — switch to second READ state, no stack change

Step 4:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
             ↑         

Stack (top to bottom):
┌───┐
│ b │
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'b': matches top of stack 'b' → POP, stack becomes [a, Δ]

Step 5:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
                 ↑     

Stack (top to bottom):
┌───┐
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'a': matches top of stack 'a' → POP, stack becomes [Δ]

Step 6:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ a │ Δ │ 
└───┴───┴───┴───┴───┴───┘
                     ↑ 

Stack (top to bottom):
┌───┐
│ Δ │
└───┘

Current State: POP
Action: End of input; stack contains only Δ (Z₀) → move to ACCEPT state

3.2.5 Rejection Behavior#

An interesting feature of this PDA is that it has no explicit rejection states. Instead, rejection occurs implicitly when the PDA blocks: meaning the machine reaches a configuration where no valid transition is possible. For example, the input is rejected in the following cases:

  • Symbol Mismatch After X: if the symbol being read doesn’t match the top of the stack.

    • Example: Input “abXbb” is rejected because:

    • After X, reads first ‘b’ and pops ‘b’ (matches)

    • Reads second ‘b’ but top of stack is ‘a’ (mismatch, PDA blocks)

  • Improper X Placement: such as missing X marker or multiple X markers

    • Example: “abab” is rejected (no X)

    • Example: “abXbXa” is rejected (multiple X)

  • Stack-Input Mismatch: not enough symbols after X to match stack contents, or too many symbols after X

    • Example: “abXb” is rejected (stack still contains ‘a’)

    • Example: “abXbaa” is rejected (input remains after stack empty)

This approach to rejection through blocking is common in PDAs and demonstrates how acceptance/rejection can be implemented without explicit reject states. Let’s see an example of rejection through blocking. The following example shows how the PDA rejects input through blocking rather than explicit reject states. When reading the second ‘b’ after X, the top of stack contains ‘a’, creating a mismatch. Since there’s no valid transition defined for this configuration, the PDA blocks and the input is rejected.

3.2.6 Code Example: Rejection Through Blocking#

Section 3.2.5 explained that this PDA has no explicit reject states — it rejects by blocking: reaching a configuration (state, input_symbol, stack_top) for which no transition δ(q, a, X) is defined.

This cell demonstrates that mechanism for the input "abXbb". The mismatch occurs at Step 5: the PDA reads 'b' from the input, but the stack top is 'a' — no transition exists for this combination, so the machine halts without accepting.

What makes Step 5 a block (not a reject state): A PDA block is different from a REJECT state. A REJECT state is an explicit state in Q that the transition function leads to. A block means δ(current_state, ‘b’, ‘a’) is simply not defined in the transition table — there is no entry for that triple. The PDA cannot proceed, so it implicitly rejects.

This is also different from how the PushdownAutomaton class in Section 2 handles it: that class prints “PDA blocks → REJECT” explicitly in code for clarity. A real (hardware or mathematical) PDA would simply halt with no output.

The five steps below use the same visualize_pda_step function defined in Section 3.2.4 (tape + stack display).

# ─────────────────────────────────────────────────────────────────────────────
# Rejection Through Blocking — PalindromeX PDA (Section 3.2.5)
#
# Input "abXbb" is rejected because the second 'b' after X does not match
# the top of stack ('a'), and no transition covers (READ, 'b', 'a').
# The PDA blocks at Step 5 — no explicit REJECT state is needed.
#
# Note: visualize_pda_step was defined in Section 3.2.4. Run that cell first.
#
# Running outside Jupyter:
#   python palindrome_rejection.py  (include visualize_pda_step definition)
# ─────────────────────────────────────────────────────────────────────────────

print("Rejection Through Blocking")
print("Input: \"abXbb\"")
print("Expected: REJECT (second 'b' after X mismatches top of stack 'a')\n")

tape = ['a', 'b', 'X', 'b', 'b', 'Δ']

# Steps 1–3 are identical to the acceptance trace: push 'a', push 'b', read 'X'
visualize_pda_step(1, tape, 0, ['Δ'],
                   'READ',
                   "Read 'a': push 'a' → stack becomes [a, Δ]")

visualize_pda_step(2, tape, 1, ['a', 'Δ'],
                   'READ',
                   "Read 'b': push 'b' → stack becomes [b, a, Δ]")

visualize_pda_step(3, tape, 2, ['b', 'a', 'Δ'],
                   'READ',
                   "Read 'X': middle marker — switch to matching phase, no stack change")

# Step 4: read first 'b' after X → pops 'b' from stack (correct match so far)
visualize_pda_step(4, tape, 3, ['b', 'a', 'Δ'],
                   'READ',
                   "Read 'b': matches top of stack 'b' → POP, stack becomes [a, Δ]")

# Step 5: read second 'b' → stack top is 'a', NOT 'b' → BLOCK
# No transition δ(READ, 'b', 'a') exists → PDA halts, input rejected
visualize_pda_step(5, tape, 4, ['a', 'Δ'],
                   'READ',
                   "Read 'b' but stack top is 'a' — MISMATCH: no valid transition → "
                   "PDA BLOCKS → INPUT REJECTED")

Rejection Through Blocking
Input: "abXbb"
Expected: REJECT (second 'b' after X mismatches top of stack 'a')

Step 1:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┴───┘
 ↑                     

Stack (top to bottom):
┌───┐
│ Δ │
└───┘

Current State: READ
Action: Read 'a': push 'a' → stack becomes [a, Δ]

Step 2:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┴───┘
     ↑                 

Stack (top to bottom):
┌───┐
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'b': push 'b' → stack becomes [b, a, Δ]

Step 3:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┴───┘
         ↑             

Stack (top to bottom):
┌───┐
│ b │
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'X': middle marker — switch to matching phase, no stack change

Step 4:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┴───┘
             ↑         

Stack (top to bottom):
┌───┐
│ b │
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'b': matches top of stack 'b' → POP, stack becomes [a, Δ]

Step 5:
Tape:
┌───┬───┬───┬───┬───┬───┐
│ a │ b │ X │ b │ b │ Δ │ 
└───┴───┴───┴───┴───┴───┘
                 ↑     

Stack (top to bottom):
┌───┐
│ a │
│ Δ │
└───┘

Current State: READ
Action: Read 'b' but stack top is 'a' — MISMATCH: no valid transition → PDA BLOCKS → INPUT REJECTED

4. Every Regular Language Can Be Accepted by a PDA#

A regular language is one that can be defined by a regular expression or a finite automaton (FA). A PDA is a more powerful computational model that extends FA by adding a stack. A PDA has two key components beyond those of a FA: a stack and the ability to manipulate it (push, pop). However, a PDA doesn’t need to use the stack to recognize a regular language. By ignoring the stack (i.e., not pushing or popping symbols), a PDA can simulate the behavior of a FA. This ensures that any regular language accepted by a finite automaton can also be accepted by a PDA.

Here is an example of a regular language that can be accepted by a PDA:

4.1 Example 1: Language {\((ab)^n | n >= 0\)}#

This language contains zero or more pairs of ‘ab’:

        flowchart TD
    accTitle: Example 1: Language {$(ab)^n | n >= 0$}
    accDescr: a diagram representing a PDA that acceptes the langauge {$(ab)^n | n >= 0$}
    START([START]) --> READ1{READ}
    READ1 -->|a| READ2{READ}
    READ2 -->|b| READ1
    READ1 -->|Δ| ACCEPT([ACCEPT])

Key Components:

  • Input alphabet Σ = {a, b}

  • Stack alphabet Γ = {Δ} (stack not used)

  • Accepts strings like: “”, “ab”, “abab”, “ababab”, etc.

  • Note: This PDA doesn’t need stack operations

5. Designing a PDA from a CFG#

5.1 CFGs and PDAs are Equally Powerful#

In formal language theory, CFGs and PDAs are equally powerful because they can recognize the same set of context-free languages. This means that for any language a CFG can generate, there is a PDA that can recognize it, and vice versa.

  • If we have a CFG that describes a language (set of valid strings), we can build a PDA that accepts the same set of strings. The PDA follows the rules of the grammar, expanding variables and checking if the string can be derived from the start symbol.

  • If we have a PDA that recognizes a language, we can create a CFG that generates the same language. The CFG will be constructed based on the transitions of the PDA, ensuring it produces only the valid strings the PDA accepts.

5.2 Systematic Approach#

When converting a Context-Free Grammar to a PDA, we can follow a systematic approach. The systematic conversion from CFG to PDA is possible due to several fundamental properties:

  • CFG productions (A → BC) directly map to PDA stack operations. When the PDA sees a variable A, it can systematically replace it with BC. This mirrors how CFG derivations work, making the conversion natural.

  • Every CFG production becomes a specific set of PDA transitions. Variables on the right side of productions become push operations, and terminal symbols become read/match operations. These mappings are consistent and predictable.

  • CFG’s recursive nature aligns with PDA’s stack mechanism. The stack naturally handles nested structures in the grammar and Last-in-first-out (LIFO) property matches derivation order.

The following diagram illustrates this systematic conversion:

        graph TD
    accTitle: Converting a Context-Free Grammar to a PDA
    accDescr: a diagram representing the process of converting a Context-Free Grammar to a PDA
    subgraph CFG[Context-Free Grammar]
        P[Production Rules]
        V[Non Terminals]
        T[Terminals]
        S[Start Symbol]
    end

    subgraph PDA[Pushdown Automaton]
        Q[States]
        I[Input Alphabet]
        G[Stack Alphabet]
        D[Transitions]
        Z[Initial Stack Symbol]
    end

    P -->|"Maps to"| D
    V -->|"Becomes"| G
    T -->|"Becomes"| I
    S -->|"Becomes"| Z

    style CFG fill:#f9f,stroke:#333
    style PDA fill:#bbf,stroke:#333

The following example shows how a production \(S → aSb\) is mapped to a transition in a PDA:

        stateDiagram-v2
    accTitle: How a production rule is mapped to a transition
    accDescr: a diagram representing how a production $S → aSb$ is mapped to a transition in a PDA
    direction TB
    
    state "CFG Production Rule" as cfg {
        direction LR
        state "S → aSb" as prod
    }
    
    state "PDA Transition" as pda {
        direction LR
        state "δ(q, ∧, S) = (q, aSb)" as trans
    }
    
    state "Before Transition" as before {
        direction TB
        state "State: q" as q1
        state "Stack Top: S" as s1
        state "Input: abc..." as i1
    }
    
    state "After Transition" as after {
        direction TB
        state "State: q" as q2
        state "Stack Top: a" as s2
        state "Middle: S" as s3
        state "Bottom: b" as s4
        state "Input: abc..." as i2
    }
    
    cfg --> pda : Maps to
    pda --> before : Applies as
    before --> after : ∧ (no input read)
    
    note right of after
        1. Pop S
        2. Push b (rightmost)
        3. Push S (middle)
        4. Push a (leftmost)
        Note: Input remains unchanged
    end note

Step 1: Convert the CFG to CNF#

Before designing the PDA, ensure the CFG is in Chomsky Normal Form (CNF): A grammar in CNF has productions of only two forms:

  1. A → BC (where A, B, C are non-terminals)

  2. A → a (where A is a non-terminal and a is a terminal)

Step 2: Beginning PDA Structure#

The PDA will have a beginning structure:

        flowchart TD
    accTitle: Beginning structure in a PDA
    accDescr: a diagram representing a beginning structure in a PDA
    START([START]) --> PUSH[PUSH S]
    PUSH --> POP{POP}

Step 3: Designing PDA Structure for Production Type ‘A → BC’#

Since the stack follows LIFO, non-terminals should be pushed in the reverse order of their respective production rule:

        flowchart TD
    accTitle: PDA Structure for Production Type 'A → BC'
    accDescr: a diagram representing PDA Structure for Production Type 'A → BC'
    POP{POP} -->|A| PUSH_C[PUSH C]
    PUSH_C --> PUSH_B[PUSH B]
    PUSH_B --> POP

Step 4: Designing PDA Structure for Production Type ‘A → a’#

        flowchart LR
    accTitle: PDA Structure for Production Type 'A → a'
    accDescr: a diagram representing PDA Structure for Production Type 'A → a'
    READ{READ} -->|a| POP{POP}
    POP -->|A| READ

Step 5: Designing PDA Structure for Accept State#

When the stack becomes empty, indicating that the last non-terminal has been converted into a terminal, the machine takes this path:

        flowchart LR
    accTitle: PDA Structure for Accept State
    accDescr: a diagram representing PDA Structure for Accept State
    POP{POP} -->|Δ| READ{READ}
    READ -->|Δ| ACCEPT([ACCEPT])

5.3 Examples: Designing a PDA from a CFG#

5.3.1 Example 1: Language: {\(b^n | n ≥ 3\)}#

Let the given CFG be in CNF as follows:

S → SB | AB
A → BB
B → b

The PDA diagram for this given CFG is illustrated below:

        stateDiagram-v2
    accTitle: PDA Structure for a given CFG
    accDescr: a diagram representing a given CFG
    direction TB
    
    START: START
    PUSH_S: PUSH S
    READ1: READ₁
    READ2: READ₂
    POP: POP
    PUSH_B1: PUSH B
    PUSH_S1: PUSH S
    PUSH_B2: PUSH B
    PUSH_A: PUSH A
    PUSH_B3: PUSH B
    PUSH_B4: PUSH B
    ACCEPT: ACCEPT

    START --> PUSH_S
    PUSH_S --> POP
    
    READ1 --> POP: b
   
    POP --> READ1: B
    POP --> READ2: Δ
    
    READ2 --> ACCEPT: Δ
    
    POP --> PUSH_B1: S
    PUSH_B1 --> PUSH_S1
    PUSH_S1 --> POP
    
    POP --> PUSH_B2: S
    PUSH_B2 --> PUSH_A
    PUSH_A --> POP
    
    POP --> PUSH_B3: A
    PUSH_B3 --> PUSH_B4
    PUSH_B4 --> POP

5.3.2 Example 2: PDA for Palindromes (Excluding ∧)#

Let’s create a PDA that recognizes palindromes (excluding ∧) over the alphabet {a, b} by the following CFG:

\(S → AR_1 | BR_2 | AA | BB\)
\(R_1 → SA\)
\(R_2 → SB\)
\(S → a | b\)
\(A → a\)
\(B → b\)

        flowchart TD
    accTitle: PDA Structure for palindromes
    accDescr: a diagram representing a PDA that recognizes palindromes (excluding ∧) over the alphabet {a, b}
    %% Style for transition labels
    classDef incomingLabel color:#9b59b6,font-weight:bold
    classDef outgoingLabel color:#e67e22,font-weight:bold

    START[START]:::start
    PUSHS1[PUSH S]:::push
    POP{POP}:::pop
    READ1{READ₁}:::read
    READ2{READ₂}:::read
    READ3{READ₃}:::read
    READ4{READ₄}:::read
    PUSHR1[PUSH R₁]:::push
    PUSHA1[PUSH A]:::push
    PUSHR2[PUSH R₂]:::push
    PUSHB1[PUSH B]:::push
    PUSHA2[PUSH A]:::push
    PUSHB2[PUSH B]:::push
    PUSHA3[PUSH A]:::push
    PUSHS2[PUSH S]:::push
    PUSHB3[PUSH B]:::push
    PUSHS3[PUSH S]:::push
    PUSHA4[PUSH A]:::push
    PUSHB4[PUSH B]:::push
    ACCEPT[ACCEPT]:::accept

    START --> PUSHS1
    PUSHS1 --> POP
    READ1 -->|"a,b"| POP:::outgoingLabel
    READ2 -->|"b"| POP:::outgoingLabel
    READ3 -->|"a"| POP:::outgoingLabel
    POP -->|"S"| READ1:::incomingLabel
    POP -->|"B"| READ2:::incomingLabel
    POP -->|"A"| READ3:::incomingLabel
    POP -->|"Δ"| READ4:::incomingLabel
    READ4 -->|"Δ"| ACCEPT:::outgoingLabel
    
    POP --> |S| PUSHR1
    PUSHR1 --> PUSHA1
    PUSHA1 --> POP
    
    POP --> |R₁| PUSHA2
    PUSHA2 --> PUSHS2
    PUSHS2 --> POP
    
    POP --> |S| PUSHR2
    PUSHR2 --> PUSHB1
    PUSHB1 --> POP
    
    POP --> |R₂| PUSHB2
    PUSHB2 --> PUSHS3
    PUSHS3 --> POP
    
    POP --> |S| PUSHA3
    PUSHA3 --> PUSHA4
    PUSHA4 --> POP
    
    POP --> |S| PUSHB3
    PUSHB3 --> PUSHB4
    PUSHB4 --> POP

    %% Add curved links with linkStyle
    linkStyle 0,1,2,3,4,5,6,7,8,9 stroke:#4a90e2,stroke-width:2px;
    linkStyle 10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27 stroke:#27ae60,stroke-width:2px;

This PDA uses distinct states for reading, pushing, and popping operations to recognize palindromes. Let’s break it down:

  • Initial Setup:

    • Starts with “START” state

    • First operation is “PUSH S”

  • Main States:

    • READ₁, READ₂, READ₃, READ₄: Reading states for input symbols

    • POP: Central state for stack operations

    • Multiple PUSH states for different combinations

  • Transition Mechanisms:

    • READ₁ can read ‘a’ or ‘b’ (denoted by a,b on its outgoing transition)

    • READ₂ specifically reads ‘b’

    • READ₃ specifically reads ‘a’

    • READ₄ reads a blank symbol before accepting

  • Stack Operations:the PDA has several push sequences:

    • PUSH R₁ → PUSH A

    • PUSH A → PUSH S

    • PUSH R₂ → PUSH B

    • PUSH B → PUSH S

    • PUSH A → PUSH A

    • PUSH B → PUSH B

  • Operation Flow: the machine starts by pushing S, it then enters a cycle of:

    • Reading input symbols (through READ states)

    • Pushing corresponding symbols and markers onto the stack

    • Using the POP state as a central control point

    • The Δ (blank symbol) transition to READ₄ represents the transition to final verification

    • Acceptance occurs after successful matching of all symbols

  • Key Features:

    • The POP state acts as a central hub for controlling transitions

    • Multiple push sequences allow for building palindrome structure

    • The use of R₁ and R₂ as markers helps track the structure of the palindrome

  • Symbol Meanings:

    • S: Stack bottom/separator marker

    • A, B: Input symbols being processed

    • R₁, R₂: Special markers for tracking palindrome structure

    • Δ: blank or Empty string transition

    • a, b: Input alphabet symbols

6. Practice Exercises#

6.1 Regular Grammar Conversion#

Modify the palindrome PDA to accept palindromes with a middle marker ‘#’

6.2 Null Production Elimination#

Implement a PDA for the language \(L = \{a^nb^n | n ≥ 0\}\)

6.3 Unit Production Elimination#

Create a PDA for the language \(L = \{ww^R\}\) where w is any string of the alphabet {a, b} and \(w^R\) is the reverse of w.

6.4 Balanced Parentheses Checker#

Design and implement a PDA that accepts strings with balanced parentheses using the alphabet {(, )}. The language is L = {w | w contains properly nested parentheses}.

Examples:

  • Accept: “”, “()”, “(())”, “()()”, “((()))”

  • Reject: “(”, “)”, “(()”, “())”

6.5 Expression Validator with Multiple Bracket Types#

Create a PDA that validates expressions with three types of brackets: (), [], {}. The brackets must be properly nested and matched.

Examples:

  • Accept: “{[()]}”, “()[]{}”, “{[(())]}”

  • Reject: “([)]”, “{[}”, “((]”

6.6 Context-Free Language Recognizer (\(a^nb^nc^n\))#

Design a PDA that recognizes the language L = {\(a^ib^jc^k \mid i = j \text{ or } j = k, i,j,k \geq 0\)}. This is a context-free language that cannot be recognized by finite automata.

Examples:

  • Accept: “abc”, “aabbcc”, “aaabbbccc”

  • Reject: “abccc”, “aaabbc”, “abbc”

6.7 CFG to PDA Converter#

Create a program that automatically converts a Context-Free Grammar to a PDA using the systematic approach described in the chapter.

6.8 PDA Simulation Environment#

Design and simulate a PDA that recognizes palindromes over {a, b} with a special middle symbol \(\#\), i.e., strings of the form: \(w\#w^R\), where \(w^R\) is the reverse of \(w\).

Examples:

  • Accept: “a#a”, “ab#ba”, “bbb#bbb”

  • Reject: “a#b”, “b#bb”, “abb#abb”

7. Further Reading#

  • “Introduction to the Theory of Computation” by Michael Sipser, Section 2.2

  • “Introduction to Computer Theory” by Daniel I.A. Cohen, Chapter 14, 15

  • “Automata Theory, Languages, and Computation” by Hopcroft, Motwani, and Ullman, Chapter 6

Contents