Introduction to Automata Theory, Languages, and Computation

Hopcroft, J. E., Jeffrey D. Ullman, I. t. A. T., & Computation, A. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.

Type

Book chapter

Intellectual base

Textbook

Year

1979

Link

https://archive.org/details/introductiontoau0000hopc

Cited from

computer_science

Cited by

5 citations across 4 artifacts.

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

Primes

• Computability
  • the limits of program-equivalence checking and program synthesis. Linguistics. The parsing problem for sufficiently general grammars (unrestricted phrase-structure grammars) is undecidable

    This sourceEstablishes that type-0 (unrestricted) phrase-structure grammars generate exactly the recursively enumerable languages and that their membership/recognition problem is undecidable — a structural reason general grammar parsing must use constrained classes.

• State and State Transition
  • The finite or infinite state space defining all possible conditions the system may occupy

Domain-specific

• Description number
  • A description number is the integer obtained by encoding a Turing machine's complete finite description according to a fixed numeral convention.
  • … and a convenient observable transfers from Turing's proof maps every standard description to a description number and lets a universal machine interpret the encoded machine and input. to A computability proof treats the particular numeral value as convention-dependent while preserving effective encoding and decoding..
• Regular Grammar
  • The active nonterminal acts like a finite control state, which is why regular grammars and finite automata characterize the same class of string languages.

    This sourceThe text treats left- and right-regular grammars and the paired finite-automaton constructions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:085294cfee15 · see in the full table