---
title: "Introduction to Automata Theory, Languages, and Computation"
authors:
  - John E. Hopcroft
  - Jeffrey D. Ullman
year: 1979
venue: Addison-Wesley
arxiv: null
doi: null
source: "https://archive.org/details/introductiontoau00hopc"
topics:
  - automata
  - formal-languages
  - hopcroft-ullman
seed_rank: 738
seed_batch: perfects-algorithms-2026-08-13
reviewed: 2026-08-13
pool: maths-foundations
relevance_score: 9
lineage: algorithms-and-complexity
cites:
  - title: Finite Automata and Their Decision Problems
    url: "https://doi.org/10.1147/rd.32.0114"
    year: 1959
    arxiv: null
    doi: 10.1147/rd.32.0114
  - title: Three Models for the Description of Language
    url: "https://doi.org/10.1109/TIT.1956.1056813"
    year: 1956
    arxiv: null
    doi: 10.1109/TIT.1956.1056813
  - title: Representation of Events in Nerve Nets and Finite Automata
    url: "https://doi.org/10.1515/9781400882618-002"
    year: 1956
    arxiv: null
    doi: 10.1515/9781400882618-002
see:
  - "619-finite-automata-and-their-decision-problems"
  - "599-three-models-for-the-description-of-language"
  - "530-representation-of-events-in-nerve-nets-and-finite-automata"
---

# Introduction to Automata Theory, Languages, and Computation

## One-sentence takeaway

The 1979 “Cinderella book” standardizes the undergraduate spine of automata, grammars, decidability, and complexity in one volume.

## Why it matters here

Broadside’s foundations pool treats NFA/DFA/CFG/TM material as shared vocabulary. This is the textbook those cards assume — constructions, pumping lemmas, and reductions in one place — not a substitute for Rabin–Scott or Chomsky.

## Key ideas

- Finite automata, regular expressions, and the Myhill–Nerode view are developed together.
- Context-free grammars, pushdown automata, and parsing sit in the middle third.
- Turing machines, undecidability, and an introduction to complexity close the book.
- Rabin–Scott, Chomsky’s three models, and Kleene’s nerve-net events are the cited primary sources.
- Addison-Wesley, 1979, ISBN 0-201-02988-X, 418 pages; later HMU editions differ.

## Caveats

## Links

- Internet Archive: https://archive.org/details/introductiontoau00hopc