Pushdown Automata (PDA)

A Pushdown Automaton (PDA) is a computational model that extends the capabilities of a Finite State Automaton (FSA) by adding an external storage structure called a stack. While regular languages can be recognized by finite automata, context-free languages (such as balanced parentheses or nested structures like $a^n b^n$) require a PDA to keep track of an arbitrary depth of nested information.

Core Concepts of a PDA

A PDA can be formally defined as a 7-tuple:

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

Where:

• $Q$: A finite set of states.
• $\Sigma$: The finite input alphabet.
• $\Gamma$: The finite stack alphabet.
• $\delta$: The transition function mapping $Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)$.
• $q_0 \in Q$: The start state.
• $Z_0 \in \Gamma$: The start stack symbol (often representing the bottom of the stack).
• $F \subseteq Q$: The set of accepting (or final) states.

Stack Operations

In each step of execution, the PDA reads an input symbol (or performs an $\epsilon$-transition), pops the top symbol off the stack, and determines its next state and what symbols to push back onto the stack:

1. Push: Write one or more symbols onto the stack.
2. Pop: Remove the top symbol from the stack (by pushing nothing/$\epsilon$).
3. No-op: Keep the stack content unchanged (by popping the top symbol and pushing the exact same symbol back).

Interactive PDA Simulator & Transition Diagram

Below is an interactive visualizer for the classic context-free language $L = \{a^n b^n \mid n \ge 1\}$.

This machine operates as follows:

• State $q_0$ (Read & Push): Reads a, pops the top stack element, and pushes two symbols back (effectively adding an A to the stack).
• Transition $q_0 \to q_1$: On reading the first b, it pops A and transitions to $q_1$.
• State $q_1$ (Match & Pop): Reads subsequent b characters, popping one A for each b.
• Transition $q_1 \to q_2$ (Accept): Once the input is exhausted and the bottom-of-the-stack marker Z is reached, it moves to the final state $q_2$.

<style>
  .pda-container {
    font-family: system-ui, -apple-system, sans-serif;
    color: var(--color-text);
    background-color: var(--color-bg);
    border: 1px solid var(--color-border);
    border-radius: 8px;
    padding: 16px;
    display: flex;
    flex-direction: column;
    gap: 16px;
  }
  .pda-header {
    display: flex;
    justify-content: space-between;
    align-items: center;
    border-bottom: 1px solid var(--color-border);
    padding-bottom: 10px;
  }
  .pda-title {
    font-size: 1.2rem;
    font-weight: bold;
    margin: 0;
  }
  .pda-layout {
    display: grid;
    grid-template-columns: 1.5fr 1fr;
    gap: 16px;
  }
  @media(max-width: 768px) {
    .pda-layout {
      grid-template-columns: 1fr;
    }
  }
  .pda-panel {
    background-color: var(--color-bg-alt);
    border: 1px solid var(--color-border);
    border-radius: 6px;
    padding: 12px;
  }
  .pda-controls {
    display: flex;
    gap: 8px;
    margin-bottom: 12px;
    flex-wrap: wrap;
  }
  .pda-btn {
    background-color: var(--color-bg);
    color: var(--color-text);
    border: 1px solid var(--color-border);
    padding: 6px 12px;
    border-radius: 4px;
    cursor: pointer;
    font-size: 0.9rem;
    transition: all 0.2s ease;
  }
  .pda-btn:hover {
    border-color: var(--color-accent);
    background-color: var(--color-bg-alt);
  }
  .pda-btn-primary {
    background-color: var(--color-accent);
    color: var(--color-bg);
    border-color: var(--color-accent);
  }
  .pda-btn-primary:hover {
    filter: brightness(0.9);
    background-color: var(--color-accent);
  }
  .input-group {
    display: flex;
    gap: 8px;
    margin-bottom: 12px;
  }
  .pda-input {
    background-color: var(--color-bg);
    color: var(--color-text);
    border: 1px solid var(--color-border);
    padding: 6px;
    border-radius: 4px;
    flex-grow: 1;
    font-family: monospace;
    font-size: 1rem;
  }
  .tape-container {
    display: flex;
    gap: 4px;
    margin-bottom: 16px;
    overflow-x: auto;
    padding: 4px 0;
  }
  .tape-cell {
    width: 32px;
    height: 32px;
    border: 1px solid var(--color-border);
    display: flex;
    align-items: center;
    justify-content: center;
    font-family: monospace;
    font-weight: bold;
    border-radius: 4px;
    background-color: var(--color-bg);
    position: relative;
    flex-shrink: 0;
  }
  .tape-cell.active {
    background-color: var(--color-accent);
    color: var(--color-bg);
    border-color: var(--color-accent);
  }
  .tape-cell.processed {
    opacity: 0.5;
  }
  .stack-container {
    display: flex;
    flex-direction: column-reverse;
    border: 2px solid var(--color-text-secondary);
    border-top: none;
    border-radius: 0 0 8px 8px;
    width: 80px;
    min-height: 200px;
    margin: 20px auto;
    padding: 4px;
    background-color: var(--color-bg);
    box-shadow: inset 0 0 10px rgba(0,0,0,0.05);
  }
  .stack-cell {
    height: 30px;
    border: 1px solid var(--color-border);
    background-color: var(--color-bg-alt);
    border-radius: 4px;
    display: flex;
    align-items: center;
    justify-content: center;
    font-family: monospace;
    font-weight: bold;
    margin-top: 2px;
    animation: slideIn 0.2s ease-out;
  }
  @keyframes slideIn {
    from { transform: translateY(-10px); opacity: 0; }
    to { transform: translateY(0); opacity: 1; }
  }
  .graph-svg {
    width: 100%;
    height: 220px;
    border: 1px solid var(--color-border);
    border-radius: 6px;
    background-color: var(--color-bg-alt);
  }
  .node {
    fill: var(--color-bg);
    stroke: var(--color-text-secondary);
    stroke-width: 2;
    transition: all 0.3s ease;
  }
  .node.active {
    stroke: var(--color-accent);
    fill: rgba(var(--color-accent), 0.1);
    stroke-width: 4;
  }
  .node.accept {
    stroke-dasharray: 2, 2;
  }
  .edge {
    stroke: var(--color-text-secondary);
    stroke-width: 1.5;
    fill: none;
  }
  .edge.active {
    stroke: var(--color-accent);
    stroke-width: 3;
  }
  .label {
    font-size: 11px;
    fill: var(--color-text);
    font-family: monospace;
  }
  .status-text {
    font-size: 0.95rem;
    font-weight: 500;
    margin: 8px 0;
    min-height: 24px;
  }
  .rules-table {
    width: 100%;
    border-collapse: collapse;
    font-size: 0.85rem;
    margin-top: 8px;
  }
  .rules-table th, .rules-table td {
    padding: 4px 6px;
    border: 1px solid var(--color-border);
    text-align: left;
  }
  .rules-table tr.active {
    background-color: rgba(0, 150, 255, 0.15);
    font-weight: bold;
  }
</style>

<div class="pda-container">
  <div class="pda-header">
    <div class="pda-title">Automata Visualizer: L = { aⁿbⁿ | n ≥ 1 }</div>
  </div>

  <div class="pda-layout">
    <!-- Left Column: Simulation and Controls -->
    <div style="display: flex; flex-direction: column; gap: 12px;">
      <div class="pda-panel">
        <label style="display:block; font-size:0.85rem; margin-bottom:4px; font-weight:bold;">Input String (a's followed by b's):</label>
        <div class="input-group">
          <input type="text" id="inputStr" class="pda-input" value="aaabbb">
          <button class="pda-btn pda-btn-primary" id="btnLoad">Load</button>
        </div>
        
        <div class="pda-controls">
          <button class="pda-btn" id="btnStep">Step</button>
          <button class="pda-btn" id="btnPlay">Play</button>
          <button class="pda-btn" id="btnReset">Reset</button>
        </div>

        <div class="status-text" id="statusMessage">Click Load or Step to begin.</div>
        
        <div style="font-size:0.85rem; font-weight:bold; margin-bottom:4px;">Input Tape:</div>
        <div class="tape-container" id="tape"></div>
      </div>

      <!-- State Transition Graph SVG -->
      <svg class="graph-svg" id="pdaGraph">
        <defs>
          <marker id="arrow" viewBox="0 0 10 10" refX="18" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse">
            <path d="M 0 1 L 10 5 L 0 9 z" fill="var(--color-text-secondary)" />
          </marker>
          <marker id="arrow-active" viewBox="0 0 10 10" refX="18" refY="5" markerWidth="6" markerHeight="6" orient="auto-start-reverse">
            <path d="M 0 1 L 10 5 L 0 9 z" fill="var(--color-accent)" />
          </marker>
        </defs>
        
        <!-- Transitions -->
        <!-- q0 loop -->
        <path d="M 75,110 C 50,70 110,70 85,110" class="edge" id="edge-loop0" marker-end="url(#arrow)" />
        <text x="80" y="65" class="label" text-anchor="middle">a, Z₀ → A Z₀</text>
        <text x="80" y="80" class="label" text-anchor="middle">a, A → A A</text>

        <!-- q0 -> q1 -->
        <path d="M 105,120 L 235,120" class="edge" id="edge-0-1" marker-end="url(#arrow)" />
        <text x="170" y="110" class="label" text-anchor="middle">b, A → ε</text>

        <!-- q1 loop -->
        <path d="M 245,110 C 220,70 280,70 255,110" class="edge" id="edge-loop1" marker-end="url(#arrow)" />
        <text x="250" y="80" class="label" text-anchor="middle">b, A → ε</text>

        <!-- q1 -> q2 -->
        <path d="M 265,120 L 395,120" class="edge" id="edge-1-2" marker-end="url(#arrow)" />
        <text x="330" y="110" class="label" text-anchor="middle">ε, Z₀ → Z₀</text>

        <!-- Nodes -->
        <!-- q0 -->
        <circle cx="85" cy="120" r="20" class="node" id="node-q0" />
        <text x="85" y="124" class="label" text-anchor="middle" font-weight="bold">q₀</text>
        <!-- Start pointer -->
        <path d="M 35,120 L 60,120" stroke="var(--color-text-secondary)" stroke-width="2" marker-end="url(#arrow)" />

        <!-- q1 -->
        <circle cx="250" cy="120" r="20" class="node" id="node-q1" />
        <text x="250" y="124" class="label" text-anchor="middle" font-weight="bold">q₁</text>

        <!-- q2 (Accept) -->
        <circle cx="410" cy="120" r="20" class="node accept" id="node-q2" />
        <circle cx="410" cy="120" r="16" class="node accept" style="fill:none;" />
        <text x="410" y="124" class="label" text-anchor="middle" font-weight="bold">q₂</text>
      </svg>
    </div>

    <!-- Right Column: Stack & Rules -->
    <div style="display: flex; flex-direction: column; gap: 12px;">
      <div class="pda-panel" style="display: flex; flex-direction: column; align-items: center;">
        <div style="font-size: 0.9rem; font-weight: bold; margin-bottom: 4px; align-self: flex-start;">Stack Status:</div>
        <div class="stack-container" id="stack"></div>
      </div>

      <div class="pda-panel">
        <div style="font-size: 0.85rem; font-weight: bold; margin-bottom: 4px;">Transition Rules Table:</div>
        <table class="rules-table">
          <thead>
            <tr>
              <th>Rule</th>
              <th>In</th>
              <th>Pop</th>
              <th>Next</th>
              <th>Push</th>
            </tr>
          </thead>
          <tbody>
            <tr id="rule-1">
              <td>q₀</td>
              <td>a</td>
              <td>Z₀</td>
              <td>q₀</td>
              <td>A Z₀</td>
            </tr>
            <tr id="rule-2">
              <td>q₀</td>
              <td>a</td>
              <td>A</td>
              <td>q₀</td>
              <td>A A</td>
            </tr>
            <tr id="rule-3">
              <td>q₀</td>
              <td>b</td>
              <td>A</td>
              <td>q₁</td>
              <td>ε (pop)</td>
            </tr>
            <tr id="rule-4">
              <td>q₁</td>
              <td>b</td>
              <td>A</td>
              <td>q₁</td>
              <td>ε (pop)</td>
            </tr>
            <tr id="rule-5">
              <td>q₁</td>
              <td>ε</td>
              <td>Z₀</td>
              <td>q₂</td>
              <td>Z₀</td>
            </tr>
          </tbody>
        </table>
      </div>
    </div>
  </div>
</div>

<script>
  let state = "q0";
  let input = "";
  let pointer = 0;
  let stack = ["Z0"];
  let playing = false;
  let intervalId = null;

  const inputEl = document.getElementById("inputStr");
  const tapeEl = document.getElementById("tape");
  const stackEl = document.getElementById("stack");
  const statusEl = document.getElementById("statusMessage");
  const btnLoad = document.getElementById("btnLoad");
  const btnStep = document.getElementById("btnStep");
  const btnPlay = document.getElementById("btnPlay");
  const btnReset = document.getElementById("btnReset");

  function initSimulator() {
    state = "q0";
    input = inputEl.value.trim();
    pointer = 0;
    stack = ["Z0"];
    updateUI();
  }

  function updateUI() {
    // 1. Render tape
    tapeEl.innerHTML = "";
    for (let i = 0; i < input.length; i++) {
      const cell = document.createElement("div");
      cell.className = "tape-cell";
      if (i === pointer) cell.classList.add("active");
      if (i < pointer) cell.classList.add("processed");
      cell.textContent = input[i];
      tapeEl.appendChild(cell);
    }
    // Add end marker cell
    const endCell = document.createElement("div");
    endCell.className = "tape-cell";
    if (pointer === input.length) endCell.classList.add("active");
    endCell.textContent = "ε";
    tapeEl.appendChild(endCell);

    // 2. Render stack
    stackEl.innerHTML = "";
    stack.forEach(symbol => {
      const cell = document.createElement("div");
      cell.className = "stack-cell";
      cell.textContent = symbol;
      stackEl.appendChild(cell);
    });

    // 3. Highlight states & graph elements
    document.querySelectorAll(".node").forEach(node => node.classList.remove("active"));
    const activeNode = document.getElementById("node-" + state);
    if (activeNode) activeNode.classList.add("active");

    // Reset edge highlights
    document.querySelectorAll(".edge").forEach(edge => {
      edge.classList.remove("active");
      edge.style.stroke = "var(--color-text-secondary)";
    });
    
    // Reset table rule highlights
    document.querySelectorAll(".rules-table tr").forEach(tr => tr.classList.remove("active"));

    // Determine and highlight next rule & edge if matching
    const topStack = stack[stack.length - 1] || null;
    const currentSymbol = pointer < input.length ? input[pointer] : "ε";
    
    let matchedRuleId = null;
    let matchedEdgeId = null;

    if (state === "q0") {
      if (currentSymbol === "a" && topStack === "Z0") {
        matchedRuleId = "rule-1";
        matchedEdgeId = "edge-loop0";
      } else if (currentSymbol === "a" && topStack === "A") {
        matchedRuleId = "rule-2";
        matchedEdgeId = "edge-loop0";
      } else if (currentSymbol === "b" && topStack === "A") {
        matchedRuleId = "rule-3";
        matchedEdgeId = "edge-0-1";
      }
    } else if (state === "q1") {
      if (currentSymbol === "b" && topStack === "A") {
        matchedRuleId = "rule-4";
        matchedEdgeId = "edge-loop1";
      } else if (currentSymbol === "ε" && topStack === "Z0") {
        matchedRuleId = "rule-5";
        matchedEdgeId = "edge-1-2";
      }
    }

    if (matchedRuleId) {
      document.getElementById(matchedRuleId).classList.add("active");
    }
    if (matchedEdgeId) {
      const edge = document.getElementById(matchedEdgeId);
      edge.classList.add("active");
      edge.style.stroke = "var(--color-accent)";
    }
  }

  function step() {
    if (state === "q2") {
      statusEl.textContent = "Simulation finished. PDA is in accepting state q₂!";
      pause();
      return;
    }

    const currentSymbol = pointer < input.length ? input[pointer] : "ε";
    const topStack = stack[stack.length - 1];

    if (!topStack) {
      statusEl.textContent = "Error: Stack is empty but machine is not in an accepting state. Rejected.";
      statusEl.style.color = "var(--color-error)";
      pause();
      return;
    }

    if (state === "q0") {
      if (currentSymbol === "a" && topStack === "Z0") {
        stack.pop();
        stack.push("Z0");
        stack.push("A");
        pointer++;
        statusEl.textContent = "Read 'a', popped 'Z₀', pushed 'A Z₀'. State remains q₀.";
        statusEl.style.color = "var(--color-text)";
      } else if (currentSymbol === "a" && topStack === "A") {
        stack.pop();
        stack.push("A");
        stack.push("A");
        pointer++;
        statusEl.textContent = "Read 'a', popped 'A', pushed 'A A'. State remains q₀.";
        statusEl.style.color = "var(--color-text)";
      } else if (currentSymbol === "b" && topStack === "A") {
        stack.pop();
        state = "q1";
        pointer++;
        statusEl.textContent = "Read 'b', popped 'A' (ε pushed). Transitioned to state q₁.";
        statusEl.style.color = "var(--color-text)";
      } else {
        statusEl.textContent = `Rejected: No transition from q₀ for symbol '${currentSymbol}' with stack top '${topStack}'.`;
        statusEl.style.color = "var(--color-error)";
        pause();
      }
    } else if (state === "q1") {
      if (currentSymbol === "b" && topStack === "A") {
        stack.pop();
        pointer++;
        statusEl.textContent = "Read 'b', popped 'A' (ε pushed). State remains q₁.";
        statusEl.style.color = "var(--color-text)";
      } else if (currentSymbol === "ε" && topStack === "Z0") {
        state = "q2";
        statusEl.textContent = "Reached end of input, popped bottom-of-stack 'Z₀'. Transitioned to final state q₂!";
        statusEl.style.color = "var(--color-success)";
        pause();
      } else {
        statusEl.textContent = `Rejected: No transition from q₁ for symbol '${currentSymbol}' with stack top '${topStack}'.`;
        statusEl.style.color = "var(--color-error)";
        pause();
      }
    }

    updateUI();
  }

  function play() {
    if (playing) {
      pause();
    } else {
      playing = true;
      btnPlay.textContent = "Pause";
      intervalId = setInterval(step, 1200);
    }
  }

  function pause() {
    playing = false;
    btnPlay.textContent = "Play";
    if (intervalId) {
      clearInterval(intervalId);
      intervalId = null;
    }
  }

  btnLoad.onclick = () => {
    pause();
    initSimulator();
    statusEl.textContent = "Loaded new string. Ready to simulate.";
    statusEl.style.color = "var(--color-text)";
  };

  btnStep.onclick = () => {
    pause();
    step();
  };

  btnPlay.onclick = play;
  btnReset.onclick = () => {
    pause();
    initSimulator();
    statusEl.textContent = "Reset complete.";
    statusEl.style.color = "var(--color-text)";
  };

  // Initial load
  initSimulator();
</script>

Comparison of PDA Variations

Like Finite State Automata, Pushdown Automata exist in both deterministic and non-deterministic forms. However, unlike FSAs, these two classes of PDAs are not equivalent in power.

Deterministic PDA (DPDA)

A Deterministic PDA has at most one choice of transition for any given state, input symbol, and stack top.

• Recognizes: Deterministic Context-Free Languages (DCFLs).
• Properties: Easily parsable in linear time. Essential for modern compiler design (e.g., LR parsers).
• Example: $L = \{a^n b^n \mid n \ge 0\}$ is deterministic.

Non-Deterministic PDA (NPDA)

An NPDA can have multiple valid transitions for a single configuration, allowing the machine to explore multiple paths simultaneously (or make "perfect guesses").

• Recognizes: All Context-Free Languages (CFLs).
• Properties: Significantly more powerful than DPDAs.
• Example: $L = \{w w^R \mid w \in \{a,b\}^*\}$ (even-length palindromes) requires non-determinism to guess where the exact center of the string lies before starting to pop symbols.