Questions: Regular Languages: Definition and Characterization

Question 1

Which of the following languages is NOT regular?

• A. The set of all strings over {a, b} that contain the substring 'ab'
• B. The set of all strings over {a, b} with even length
• C. The set of strings of the form aⁿbⁿ where n ≥ 0 (equal numbers of a's followed by b's)
• D. The set of all strings over {a, b} that begin with 'a'

Answer: (C)

Recognizing {aⁿbⁿ} requires counting how many a's appeared in order to verify the same number of b's follows — and that count can grow without bound, exceeding what any finite set of states can represent. Options A, B, and D are all regular: 'contains ab' is recognized by a DFA that watches for the two-character sequence; 'even length' alternates between two states; 'starts with a' checks only the first symbol.

Question 2

Why can no finite automaton recognize the language {aⁿbⁿ | n ≥ 0}?

• A. Because DFAs cannot process strings that contain both a's and b's
• B. Because regular expressions cannot use variables like n
• C. Because recognizing the language requires remembering how many a's were read, and that count can grow without bound while a DFA has only finitely many states
• D. Because the language is infinite, and finite automata can only recognize finite languages

Answer: (C)

The key is memory. To accept 'aabb' you must verify that 2 b's follow 2 a's — so you must remember the count while reading the b's. Since n can be any positive integer, you need unbounded memory. A DFA with k states can only distinguish k different 'situations' — it cannot represent arbitrarily large counts. Option D is wrong: many infinite languages (like 'all strings containing ab') are regular.

Question 3

A nondeterministic finite automaton (NFA) can recognize languages that no deterministic finite automaton (DFA) can recognize.

• T. True
• F. False

Answer: False

NFAs and DFAs are equivalent in power: every NFA can be converted to a DFA that recognizes exactly the same language, via the subset construction. NFAs are often smaller and easier to design, but they do not expand the class of recognizable languages. Both recognize exactly the regular languages — no more, no less.

Question 4

Regular languages are characterized by the ability to be recognized using only a constant amount of memory, regardless of how long the input string is.

• T. True
• F. False

Answer: True

A DFA with n states processes any input string — of length 10, 10,000, or 10 billion — using the same fixed set of states. No additional memory is allocated as input length grows. This constant-memory property is what makes regular languages computationally cheap and what limits their expressive power: anything requiring counting or matching over unbounded distances exceeds what finite memory can handle.

Question 5

Explain in your own words why three seemingly different formalisms — DFAs, regular expressions, and right-linear grammars — all define exactly the same class of languages.

Model answer: Each formalism is a different way to describe the same underlying constraint: what patterns can be recognized or generated using only finite, constant memory. DFAs make this explicit through fixed state sets; regular expressions describe the same patterns through concatenation, union, and Kleene star; right-linear grammars generate these patterns through a restricted production rule structure. Their equivalence is proven by showing how to convert each representation into the others — any language expressible in one form is expressible in all three.

The practical implication is freedom of representation: use whichever formalism is most convenient. Regular expressions are compact and human-readable; DFAs are efficient to execute; NFAs are often easier to construct. The underlying class — regular languages — is fixed by the constant-memory constraint, and the three formalisms are different lenses on the same mathematical object.