Which Automaton Accepts Regular Languages? The Correct Answer Is DFA

In formal language theory, the automaton that accepts regular languages is the DFA, i.e., option (ii).2 A finite automaton has only finitely many states, and this finite memory matches exactly the expressive power of regular languages.2

By contrast, the other options correspond to strictly different language classes in the Chomsky hierarchy:

• PDA accepts context-free languages, not exactly regular languages.2
• Turing machine recognizes recursively enumerable languages, a much broader class.
• LBA accepts context-sensitive languages, also more powerful than regular languages.2

So for the multiple-choice question:

Therefore, the correct answer is (ii) DFA.2

A useful way to remember this is:

$$\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}$$

And the corresponding machine models are:

$$\text{DFA/NFA} \;\rightarrow\; \text{PDA} \;\rightarrow\; \text{LBA} \;\rightarrow\; \text{Turing Machine}$$

Footnotes

1. Regular Languages and Finite Automata - Cambridge lecture notes stating that a language is regular iff it is accepted by some deterministic finite automaton. ↩ ↩² ↩³

2. Formal Languages, Automata and Computation - andrew.cmu.edu - CMU slides explicitly stating that DFAs accept regular languages. ↩ ↩²

3. Chapter 1 Basics of Formal Language Theory - UPenn notes defining regular languages as those accepted by some DFA and explaining DFA acceptance. ↩

4. 1 Push-down Automata and Context-Free Languages - UNC notes showing that PDAs recognize exactly the context-free languages. ↩

5. Context Sensitive Grammars and Linear Bounded Automata - IISc seminar notes summarizing the Chomsky hierarchy and matching DFA/PDA/LBA/Turing machine to their language classes. ↩ ↩² ↩³

6. Grammars, Recursively Enumerable Languages, and Turing Machines - UT Austin notes stating that context-sensitive languages are exactly the languages accepted by linear bounded automata. ↩

A precise theorem often used in automata theory states:

A language is regular if and only if it is accepted by some DFA.2

This “if and only if” statement is important. It means two things simultaneously:2

1. Every DFA language is regular.
2. Every regular language can be recognized by some DFA.

This is why DFA is not just an automaton that can accept some regular languages; it is the canonical automaton for them.2

Formally, if a DFA is written as

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

then the language accepted by $M$ is

$$L(M) = \{\, w \in \Sigma^* \mid \delta^*(q_0, w) \in F \,\}.$$

Here:

• $Q$ is the finite set of states,
• $\Sigma$ is the input alphabet,
• $\delta$ is the transition function,
• $q_0$ is the start state,
• $F$ is the set of accepting states.2

The key limitation is that the machine has only finite memory. Because of that, it can recognize patterns like:

• strings ending in 01,
• strings containing abb,
• strings with an even number of 1s,2

but it cannot recognize patterns requiring unbounded counting such as

$$\{a^n b^n \mid n \ge 0\},$$

which is not regular.

Footnotes

1. Regular Languages and Finite Automata - Cambridge lecture notes stating that a language is regular iff it is accepted by some deterministic finite automaton. ↩ ↩² ↩³

2. Formal Languages, Automata and Computation - andrew.cmu.edu - CMU slides explicitly stating that DFAs accept regular languages. ↩ ↩² ↩³

3. Chapter 1 Basics of Formal Language Theory - UPenn notes defining regular languages as those accepted by some DFA and explaining DFA acceptance. ↩ ↩²

4. Finite Automata Outline Deterministic ... - Carnegie Mellon University - CMU lecture notes explaining DFA membership and giving examples of regular and non-regular languages. ↩ ↩² ↩³

The distractors in this question are educational because each one is associated with a different computational capability.

Why not PDA?

A pushdown automaton recognizes context-free languages.2 Since every regular language is also context-free, a PDA can accept regular languages, but that is not the best answer to the question. The question asks for the automaton class associated with regular languages exactly, and that is DFA.2

Why not Turing machine?

A Turing machine is far more powerful than a DFA and recognizes recursively enumerable languages. Because it is more general, it can accept regular languages too, but again it does not characterize the class exactly.

Why not LBA?

A linear bounded automaton recognizes context-sensitive languages.2 This is also a stronger model than a DFA, so it is not the standard answer.

Thus, the distinction is:

• Can accept some regular languages? Many stronger machines can.
• Characterizes the class of regular languages? DFA.2

Footnotes

1. 1 Push-down Automata and Context-Free Languages - UNC notes showing that PDAs recognize exactly the context-free languages. ↩

2. Context Sensitive Grammars and Linear Bounded Automata - IISc seminar notes summarizing the Chomsky hierarchy and matching DFA/PDA/LBA/Turing machine to their language classes. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Regular Languages and Finite Automata - Cambridge lecture notes stating that a language is regular iff it is accepted by some deterministic finite automaton. ↩ ↩²

4. Formal Languages, Automata and Computation - andrew.cmu.edu - CMU slides explicitly stating that DFAs accept regular languages. ↩ ↩²

5. Grammars, Recursively Enumerable Languages, and Turing Machines - UT Austin notes stating that context-sensitive languages are exactly the languages accepted by linear bounded automata. ↩

A compact conceptual summary is:

• A DFA has only states as memory.2
• A PDA has states + stack.2
• An LBA has bounded tape.2
• A Turing machine has general tape-based computation.

That extra memory increases recognition power. This is why the machines correspond to increasingly expressive language classes.2

For exam settings, you can memorize the mapping:

Hence the final answer remains:

$$\boxed{\text{(ii) DFA}}$$

Footnotes

1. Regular Languages and Finite Automata - Cambridge lecture notes stating that a language is regular iff it is accepted by some deterministic finite automaton. ↩

2. Chapter 1 Basics of Formal Language Theory - UPenn notes defining regular languages as those accepted by some DFA and explaining DFA acceptance. ↩

3. 1 Push-down Automata and Context-Free Languages - UNC notes showing that PDAs recognize exactly the context-free languages. ↩

4. Context Sensitive Grammars and Linear Bounded Automata - IISc seminar notes summarizing the Chomsky hierarchy and matching DFA/PDA/LBA/Turing machine to their language classes. ↩ ↩² ↩³ ↩⁴

5. Grammars, Recursively Enumerable Languages, and Turing Machines - UT Austin notes stating that context-sensitive languages are exactly the languages accepted by linear bounded automata. ↩ ↩²