The lexical analysis for a modern computer language such as Java needs the…
2011
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
- A.
Finite state automata
- B.
Deterministic pushdown automata
- C.
Non-deterministic pushdown automata
- D.
Turing machine
Attempted by 291 students.
Show answer & explanation
Correct answer: A
Answer: Finite state automata
Why: Lexical grammars that define tokens are regular languages (they are written using regular expressions). Regular languages are exactly those recognized by finite automata, so finite automata provide both the necessary and sufficient computational power for lexical analysis.
Any token pattern expressed by a regular expression can be converted into a finite automaton (NFA → DFA).
Finite automata cannot recognize non-regular (context-free or worse) languages, but lexical analysis does not require that extra power.
In practice, lexers use deterministic finite automata for efficient longest-match and priority-based token recognition.
A video solution is available for this question — log in and enroll to watch it.