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.
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.
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.
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
Distinguishability and minimal deterministic automata
Build the minimal DFA from residual languages and compute it by partition refinement.
- 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.
- 1.3
Decision problems for deterministic finite automata
Decide emptiness, equivalence and infinitude using finite graph searches.
- 1.4
The regular-language pumping lemma
Use finite-state repetition and correct quantifiers to prove languages nonregular.
- 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
- 2.1
Pushdown automata: final-state and empty-stack acceptance
Convert between two nondeterministic pushdown acceptance conventions while preserving the language.
- 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.
- 2.3
Context-free membership by dynamic programming
Derive the CYK table for a grammar in Chomsky normal form.
- 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.
- 2.5
Simplifying context-free grammars
Eliminate empty and unit productions while preserving the language.
- 2.6
Converting a grammar to Chomsky normal form
Preserve a context-free language while separating terminals and binarizing productions.
- 2.7
The pumping lemma for context-free languages
Derive the context-free pumping lemma from parse trees and use its quantifiers correctly.
- 2.8
Context-free languages and regular constraints
Combine a pushdown automaton with a finite automaton and examine closure limits.
- 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
- 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.
- 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
- 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
- 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.
- 5.2
Undecidability: self-reference and a halting reduction
Distinguish recognition from decision and reduce arbitrary-input halting to empty-input halting.
- 5.3
Rice's theorem and semantic properties
Reduce halting to nontrivial properties of recognizable languages.
- 5.4
Why Post correspondence is undecidable
Encode accepting computations as correspondence sequences and remove the forced-first-tile condition.
- 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
- 6.1
Finite automata: states as invariants
Construct and justify a deterministic automaton for parity, then distinguish its states.
- 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
- 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
- 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
- 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.