Questions: Limitations of Finite Automata and Non-Regular Languages

Question 1

Why can't a finite automaton recognize the language {aⁿbⁿ | n ≥ 0} — strings of n a's followed by exactly n b's?

• A. Finite automata can only process single-character alphabets
• B. The language requires the machine to count an arbitrarily large n and verify a match, but a finite automaton's entire memory is its current state — a fixed, finite set that cannot store unbounded counts
• C. This language is actually regular; it just requires building a very large number of states
• D. Finite automata cannot process strings that contain two different character types

Answer: (B)

A finite automaton with k states can distinguish at most k different input histories. To recognize {aⁿbⁿ}, the machine must remember the exact count of a's read so far and verify that the b's match — but once n > k, the machine has visited some state before and has lost track of the exact count. No finite k is sufficient for all n. This is not a design flaw; it is a precise statement about what bounded-memory machines can and cannot do. The pumping lemma formalizes this exact argument.

Question 2

A pushdown automaton extends a finite automaton by adding a stack. What specific problem does the stack solve?

• A. It allows the machine to run faster on long inputs by caching recent characters
• B. It allows non-deterministic transitions between states
• C. The stack provides unbounded memory, enabling the machine to count and match structures like aⁿbⁿ that exceed any fixed state bound
• D. It allows the machine to recognize regular languages with fewer states

Answer: (C)

The stack solves the unbounded memory problem. A pushdown automaton reading {aⁿbⁿ} pushes a symbol onto the stack for each a it reads, then pops a symbol for each b. If the stack is empty exactly when the input ends, the counts matched. The stack can grow to any depth, so there is no fixed limit n beyond which the machine loses count. This is why adding a stack moves you from regular languages (finite automata) to context-free languages (pushdown automata) — it adds exactly the memory capability that finite automata lack.

Question 3

Any language with a simple, concise description can be recognized by a finite automaton.

• T. True
• F. False

Answer: False

Simplicity of description has no bearing on regularity. The language {aⁿbⁿ | n ≥ 0} has a simple one-line description, but it requires unbounded memory to recognize and is definitively non-regular. Similarly, balanced parentheses have a simple description and are non-regular. What matters for regularity is whether membership depends only on a finite classification of prefixes — not how tersely the language can be described.

Question 4

The inability of finite automata to recognize languages like {aⁿbⁿ} is a precise characterization of their computational power, not simply an engineering limitation that could be fixed with a better design.

• T. True
• F. False

Answer: True

This is the key theoretical insight. It is not that existing finite automata are poorly designed — it is that any machine with a fixed, finite number of states will face this limitation for any language requiring unbounded counting or matching. The pumping lemma proves this for the entire class of finite automata, not just specific designs. Understanding this as a fundamental boundary, not an engineering deficiency, is what motivates the Chomsky hierarchy: each level adds memory capability that the level below provably cannot simulate.

Question 5

Explain, in terms of states, why a finite automaton cannot count to an arbitrary n, no matter how many states it has.

Model answer: A finite automaton with k states can be in at most k distinct configurations. Its 'memory' of everything it has read so far is entirely encoded in which of those k states it currently occupies. To count exactly to n for an arbitrary n, the machine would need at least n+1 distinct states (one for each possible count from 0 to n). But k is fixed before the machine runs, so for any input with more than k a's, the machine must revisit a state it has already been in — meaning it cannot distinguish, say, 'I've read 47 a's' from 'I've read 52 a's.' No matter how large you make k, there is always an input long enough to exhaust the states.

The Myhill-Nerode theorem formalizes this intuition: a language is regular if and only if it partitions all possible input strings into finitely many equivalence classes based on their future behavior. Languages that require distinguishing infinitely many distinct histories (one per count n) cannot be captured by any finite partition — and therefore cannot be recognized by any finite automaton.