Skip to content

CSCI3130

Formal Languages and Automata Theory

Finite automata and regular languages, context-free grammars and pushdown automata, parsing, context-sensitive languages, Turing machines and undecidability.

9 chapters · 27 sectionsEN · 繁 · 简
My course notes

Your progress

0/ 27 sections marked complete

Next section: Distinguishability and minimal deterministic automata

Completion marks are saved in this browser.

This course in the web

In the CSCI3130 notes

Theorem cards
77
Definitions
61
Counterexamples
34
Concept lenses
13
Histories of ideas
0
Proof X-rays
33

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 27 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.

In the webTheorem cards 77 · Definitions 61 · Counterexamples 34 · Concept lenses 13 · Proof X-rays 33

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

Counts cover the 27 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.

Chapter 1 · 5 sections

Regular languages

Regular languages

Theorems 16 · Definitions 14Counterexamples 8Lenses 1Proof X-rays 6

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 1.1

    Distinguishability and minimal deterministic automata

    Build the minimal DFA from residual languages and compute it by partition refinement.

  2. 1.2

    Finite automata, regular expressions, and the pumping lemma

    Define DFAs, NFAs and regular expressions, prove the subset, Thompson and state-elimination constructions, and prove the pumping lemma and a distinguishability lower bound.

  3. 1.3

    Decision problems for deterministic finite automata

    Decide emptiness, equivalence and infinitude using finite graph searches.

  4. 1.4

    The regular-language pumping lemma

    Use finite-state repetition and correct quantifiers to prove languages nonregular.

  5. 1.5

    Homomorphisms and regular languages

    Construct finite automata for homomorphic images and inverse images.

Chapter 2 · 9 sections

Context-free languages

Context-free languages

Theorems 21 · Definitions 13Counterexamples 11Lenses 3Proof X-rays 10

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 2.1

    Pushdown automata: final-state and empty-stack acceptance

    Convert between two nondeterministic pushdown acceptance conventions while preserving the language.

  2. 2.2

    Normal forms and the grammar hidden in a stack computation

    Prove the context-free normal-form theorem, justify the pumping lemma's binary-tree hypothesis, and construct a grammar from an arbitrary nondeterministic pushdown automaton.

  3. 2.3

    Context-free membership by dynamic programming

    Derive the CYK table for a grammar in Chomsky normal form.

  4. 2.4

    Context-free grammars, stack automata, and the pumping lemma

    Derivations, parse trees and ambiguity; balanced-parenthesis and a^n b^n grammars; the simulation of a grammar by a nondeterministic pushdown automaton; the context-free pumping lemma and its limits.

  5. 2.5

    Simplifying context-free grammars

    Eliminate empty and unit productions while preserving the language.

  6. 2.6

    Converting a grammar to Chomsky normal form

    Preserve a context-free language while separating terminals and binarizing productions.

  7. 2.7

    The pumping lemma for context-free languages

    Derive the context-free pumping lemma from parse trees and use its quantifiers correctly.

  8. 2.8

    Context-free languages and regular constraints

    Combine a pushdown automaton with a finite automaton and examine closure limits.

  9. 2.9

    Deterministic pushdown automata and acceptance

    Trace a deterministic stack machine and prove the prefix restriction of empty-stack acceptance.

Chapter 3 · 2 sections

Parsing

Parsing

Theorems 6 · Definitions 7Counterexamples 2Lenses 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 3.1

    LR(0) items, shift-reduce parsing, and lookahead

    Augmented grammars, LR(0) items, closure and goto, the canonical collection, ACTION/GOTO tables and conflicts, a complete table and parse, and the distinction between LR(0) and LR(1) via S -> a | ab.

  2. 3.2

    Predictive parsing and LL(1) tables

    Build a predictive parsing table from nullable, FIRST and FOLLOW information.

Chapter 4 · 1 section

Context-sensitive languages

Context-sensitive languages

Theorems 5 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 4.1

    Noncontracting grammars and linear bounded tapes

    Noncontracting grammars and the length lemma, a complete grammar for a^n b^n c^n with an invariant proof, linear bounded automata, decidability of bounded-tape acceptance, simulation of a grammar by reverse derivations, and a marking algorithm.

Chapter 5 · 5 sections

Computability

Computability

Theorems 15 · Definitions 13Counterexamples 5Lenses 2Proof X-rays 7

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 5.1

    Turing machines, decidability, and undecidability

    Turing machine configurations, universal simulation, recognizers versus deciders, the complement theorem by dovetailing, the diagonal proof for self-acceptance, correct reduction directions, Rice's theorem, and the place of these language classes in a chain.

  2. 5.2

    Undecidability: self-reference and a halting reduction

    Distinguish recognition from decision and reduce arbitrary-input halting to empty-input halting.

  3. 5.3

    Rice's theorem and semantic properties

    Reduce halting to nontrivial properties of recognizable languages.

  4. 5.4

    Why Post correspondence is undecidable

    Encode accepting computations as correspondence sequences and remove the forced-first-tile condition.

  5. 5.5

    Why context-free grammar universality is undecidable

    Use correspondence tiles and deterministic stack comparison to reduce to grammar universality.

Chapter 6 · 2 sections

Automata worked examples

Automata worked examples

Theorems 4 · Definitions 4Counterexamples 3Lenses 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 6.1

    Finite automata: states as invariants

    Construct and justify a deterministic automaton for parity, then distinguish its states.

  2. 6.2

    Nondeterminism, ε-closure and subset construction

    Track every possible NFA state, account for empty transitions, and prove that a DFA of subsets recognizes the same language.

Chapter 7 · 1 section

Regular constraints

Combine finite-state conditions with context-free derivations.

Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 7.1

    Context-free languages under regular constraints

    Construct a context-free grammar for the intersection of a context-free language and a regular language.

Chapter 8 · 1 section

Balanced words and grammar ambiguity

Parse trees, first-return decomposition and ambiguity.

Theorems 6 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 8.1

    Context-free grammars: parse trees, ambiguity and balanced words

    Prove a grammar generates balanced words, investigate ambiguity and use first-return decomposition.

Chapter 9 · 1 section

Pushdown automata

Prove stack invariants and nondeterministic recognition.

Theorems 2 · Definitions 2Counterexamples 2Proof X-rays 2

Chapter outline →See this chapter on the web →Not yet indexed in the web

  1. 9.1

    Pushdown automata: stack invariants and guessing the middle

    Trace a stack machine for equal blocks, prove its language in both directions, and use nondeterminism carefully to recognize even palindromes.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details