A Pushdown Automaton (PDA) extends a Finite State Machine by adding a stack as auxiliary memory. This extra storage allows PDAs to recognize context-free languages that simple FSMs cannot handle. A classic example is the language aⁿBⁿ — strings consisting of exactly n copies of ‘a’ followed by n copies of ‘b’, for any n ≥ 1. The PDA pushes an ‘a’ onto the stack for every ‘a’ it reads, then pops one entry for every ‘b’. If the stack is empty exactly when all input is consumed, the string is accepted.

Pushdown Automaton for aⁿbⁿ in Java

import java.io.*;

class PushDownAutomaton {

    static char[] stack    = new char[20]; // The PDA stack storing pushed 'a' characters
    static int    stackTop = 0;             // Index pointing to the next empty slot on the stack

    /** Push a character onto the stack */
    static void push(char symbol) {
        stack[stackTop] = symbol;
        stackTop++;
    }

    /** Pop the top character from the stack (decrements the stack pointer) */
    static void pop() {
        stackTop--;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter String (e.g. aaabbb):");
        String inputString = reader.readLine();

        boolean isRejected = false;  // set to true if 'a' appears after a 'b' is seen
        int charIndex;

        // Phase 1: push every leading 'a' onto the stack
        for (charIndex = 0; charIndex < inputString.length(); charIndex++) {
            if (inputString.charAt(charIndex) == 'a') {
                push('a');
            } else {
                break;  // first 'b' encountered -- switch to popping phase
            }
        }

        // Phase 2: for every 'b', pop one 'a' from the stack
        for (; charIndex < inputString.length(); charIndex++) {
            if (inputString.charAt(charIndex) == 'a') {
                // An 'a' appearing after a 'b' is invalid for this language
                isRejected = true;
                break;
            } else {
                pop();  // one 'b' cancels one 'a'
            }
        }

        // Accepted only if the stack is empty (equal a's and b's) and no out-of-order 'a'
        if (stackTop == 0 && !isRejected) {
            System.out.println("String Accepted (equal number of a's and b's)");
        } else {
            System.out.println("String Rejected");
        }
    }
}

How the Code Works

1. The stack is a simple character array with stackTop acting as the stack pointer. push() stores the symbol and increments the pointer; pop() decrements it.
2. Phase 1 — the first for loop scans the input and pushes every ‘a’ it encounters. The moment it sees a non-‘a’ character, it breaks to begin the popping phase.
3. Phase 2 — the second for loop pops one stack entry for every ‘b’. If it encounters an ‘a’ here (e.g., input aabba), it sets isRejected = true and stops.
4. Acceptance condition: the string is accepted if and only if stackTop == 0 (every pushed ‘a’ was cancelled by a ‘b’) and isRejected is still false (no ‘a’ appeared out of order).

Sample Output

Enter String (e.g. aaabbb):
aaabbb
String Accepted (equal number of a's and b's)

Enter String (e.g. aaabbb):
aaabb
String Rejected

Output Explanation

1. For aaabbb: Three ‘a’s are pushed → stack has 3 entries. Three ‘b’s pop them one by one → stack is empty. stackTop == 0 and isRejected == false → Accepted.
2. For aaabb: Three ‘a’s are pushed → stack has 3 entries. Two ‘b’s pop two entries → stackTop == 1 (one unmatched ‘a’ remains). stackTop != 0 → Rejected.
3. Any string like aabba would also be rejected because the ‘a’ appears after a ‘b’, triggering isRejected = true.

See Also

• Turing Machine: Well-Formedness of Parenthesis in Java
• Illustrating Epsilon Closure in Java
• Finite State Machine: Check Whether String Contains ‘abb’ or not
• Finite State Machine: Check Whether String Ends with ‘abb’ or not
• Finite State Machine: Implementing Binary Adder in Java

Conclusion

Pushdown Automata are the computational backbone behind context-free grammars and parsers. By using a stack, the PDA can count and match symbols in a way that finite-state machines simply cannot. This aⁿbⁿ example is the simplest demonstration of that power, and the pattern extends naturally to more complex balanced-language recognition problems like matching parentheses, XML tags, or nested structures.