Introduction to Automata Theory, Languages, and Computation¶

Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Pearson.

Type: Book
Intellectual base: Textbook
Year: 2006
Pages cited: 1-4
Link: https://archive.org/details/trent_0116301269779
Cited from: computer_science, linguistics_semiotics, mathematics

Cited by¶

7 citations across 7 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes¶

Closure
- The regular languages are closed under union, intersection, complement, concatenation, Kleene star, reversal, and homomorphism — the strong closure properties make regular languages the canonical "well-behaved" class of formal languages, and many algorithmic results in compiler design and string processing rely on these closures, as Hopcroft, Motwani, and Ullman (2006) catalogue in their canonical automata-theory textbook.
  This sourceStandard automata-theory text cataloguing the closure-properties profiles of regular, context-free, and recursively-enumerable language classes.
Local Sequence Legality
- Formal grammars and parsing: regular expressions, context-free grammars, and programming-language tokenisation, where legality is decided before semantic analysis.
  This sourceRegular versus context-free languages; the pumping lemma showing a regular grammar cannot match balanced parentheses at arbitrary depth.
Rule of Least Power (Minimum Sufficient Capability)
- The power-ordered mechanism space is the Chomsky hierarchy: regular expressions below context-free grammars below Turing-complete code.
  This sourceStandard reference for the Chomsky hierarchy (regular ⊂ context-free ⊂ recursively enumerable) and the guaranteed linear-time, halting behavior of finite automata.

Domain-specific¶

Deterministic Finite Automaton
- Because each state-symbol pair has exactly one successor, the run is unique; the word is accepted precisely when that run ends in F.
Emptiness problem
- Emptiness problem is a decision problem asking whether the language denoted by a given formal representation contains no valid strings.
Formal Language
- This language–presentation separation is what makes closure, equivalence, expressiveness, decidability, and complexity questions precise.
Regular Grammar
- Textbooks differ about whether unit productions, empty productions, multi-terminal (w), or only \(S\to\varepsilon\) are admitted, so a rigorous use must state its convention.
  This sourceExercise 5.1.4 gives the extended right-linear forms \(A\to wB\) and \(A\to w\) and the automaton equivalence.

Verification¶

Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.

Does it back the claim? Not recorded. Neither this nor any other of the 7 citations of this work carries a recorded support check.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Links previously used in the corpus¶

Before the registry existed this work was also linked 3 other ways.

Registry ID ref:4f4856a4ab4b · see in the full table