Questions: Regular Language Recognition Algorithms

Question 1

A DFA has 500,000 states and is used to recognize a regular language. How does its size affect the time complexity of testing whether an input string of length n is in the language?

• A. It increases the time complexity to O(n × 500,000)
• B. It has no effect — DFA membership testing is O(n) regardless of the number of states
• C. It causes exponential slowdown because more states mean more possible paths
• D. It reduces the time complexity because larger DFAs can skip ahead in the input

Answer: (B)

DFA membership testing is O(n) regardless of the DFA's size. Each input symbol requires exactly one transition lookup (the DFA is deterministic — there is never a choice of transitions). Whether the DFA has 5 states or 5 million, processing one symbol always takes constant time. The state count affects memory usage and construction time, but not the per-symbol processing cost. This linear-time guarantee is one of the key advantages of DFAs over more powerful models of computation.

Question 2

A compiler lexer needs to tokenize millions of lines of source code using patterns for keywords, identifiers, and literals. Why does it precompile those patterns from NFAs to DFAs rather than using on-the-fly NFA simulation?

• A. Because NFAs cannot recognize the same languages as DFAs
• B. Because the DFA is built once at compiler construction time and then processes all subsequent input in O(n) per token, while NFA simulation pays overhead proportional to active states on every input
• C. Because NFAs require exponential time even for short inputs
• D. Because DFAs can recognize languages that NFAs cannot, enabling more expressive token patterns

Answer: (B)

NFAs and DFAs recognize the same class of languages, so expressiveness is not the issue. The tradeoff is about upfront cost vs per-query cost. Precompiling the NFA to a DFA takes time and space (potentially exponential in the number of NFA states), but once built, the DFA processes each character in constant time. For a lexer, the patterns are fixed at compiler construction time and then used to scan enormous amounts of source code — the high upfront cost is paid once, and the O(n) per-token speed is exploited millions of times. On-the-fly NFA simulation avoids the exponential blowup but pays a per-symbol overhead proportional to active states on every single token.

Question 3

DFA membership testing runs in O(n) time where n is the input length, regardless of how many states the DFA has.

• T. True
• F. False

Answer: True

True. The DFA processes one input symbol at a time, and at each step follows exactly one deterministic transition from the current state to the next. This single transition lookup is O(1). Over n symbols, the total cost is O(n). The number of states in the DFA determines memory consumption and potentially the cost of building the DFA, but has no effect on the per-symbol cost of simulation once the DFA is built.

Question 4

On-the-fly NFA simulation is generally slower than DFA simulation for any input, because tracking sets of active states takes more work per symbol than following a single transition.

• T. True
• F. False

Answer: False

False. While NFA simulation is asymptotically slower — O(n·s²) vs O(n) for a DFA with s NFA states — this comparison assumes the DFA has already been built. Precompiling an NFA to a DFA can produce a DFA with up to 2ˢ states (exponential blowup), which may be too large to construct or store. On-the-fly NFA simulation avoids this blowup entirely. For one-off queries on an NFA with a modest number of states, simulation can be faster in practice than paying the exponential upfront cost of full DFA construction. The Thompson NFA algorithm, used by some regex engines, also avoids the catastrophic backtracking of naive NFA implementations.

Question 5

Why do compiler lexers typically precompile regex patterns to DFAs, while many general-purpose regex engines (like Python's or JavaScript's) use NFA-based simulation? What practical feature drives the tradeoff?

Model answer: Compiler lexers precompile to DFAs because their patterns are fixed at construction time and used to scan enormous amounts of input — the exponential upfront cost of DFA construction is paid once, then O(n) per-token speed is exploited millions of times. General-purpose regex engines use NFA-based simulation to support features like backreferences that go beyond regular languages. Backreferences (e.g., matching a string that repeats itself) cannot be recognized by any DFA or NFA, so regex engines use a more powerful backtracking NFA model. This extra power comes at a cost: naive backtracking NFA engines can have exponential worst-case behavior on certain inputs, a problem the Thompson NFA simulation avoids by tracking all active states simultaneously.

The key insight is that the regular/NFA/DFA framework is the theory, but practical regex engines often implement slightly more powerful models (with backreferences) that break the O(n) guarantee. Understanding the DFA/NFA tradeoff helps explain why regex patterns can catastrophically slow down (ReDoS attacks exploit this) and why lexer tools choose DFA precompilation.