This work is licensed under a Creative Commons License.
Ernest Ackermann Department of Computer Science, Mary Washington College
CPSC 110 | CPSC 326
Bibliographic Information:
CHAPTER 1: FUNDAMENTALS
1.1 Alphabets
1.2 Strings
1.3 Languages
CHAPTER 2: FINITE AUTOMATA
2.1 Man Wolf Goat Cabbage
2.2 Not Getting Stuck
2.3 Deterministic Finite Automata
2.4 The 5-Tuple
2.5 The Language Accepted by a DFA
CHAPTER 3: CLOSURE PROPERTIES FOR REGULAR LANGUAGES
3.1 Closed Under Complement
3.2 Closed Under Intersection
3.3 Closed Under Union
3.4 DFA Proofs Using Induction
3.5 A Mystery DFA
CHAPTER 4: DFA APPLICATIONS
4.1 DFA Applications
4.2 A DFA-Based Text Filter in Java
4.3 Table-Driven Alternatives
CHAPTER 5: NONDETERMINISTIC FINITE AUTOMATA
5.1 Relaxing a Requirement
5.2 Spontaneous Transitions
5.3 Nondeterminism
5.4 The 5-Tuple for an NFA
5.5 The Language Accepted by an NFA
CHAPTER 6: NFA APPLICATIONS
6.1 NFA Implemented With Backtracking Search
6.2 NFA Implemented With Bit-Mapped Parallel Search
6.3 The Subset Construction
6.4 NFAs Are Exactly As Powerful As DFAs
6.5 DFA Or NFA?
Press Spacebar to continue
CHAPTER 7: REGULAR EXPRESSIONS
7.1 Regular Expressions, Formally Defined
7.2 Regular Expression Examples
7.3 For Every Regular Expression, a Regular Language
7.4 Regular Expressions and Structural Induction
7.5 For Every Regular Language, a Regular Expression
CHAPTER 8: REGULAR EXPRESSION APPLICATIONS
8.1 The egrep Tool
8.2 Non-Regular Regexps
8.3 Implementing Regexps
8.4 Regular Expressions in Java
8.5 The lex Tool
CHAPTER 9: ADVANCED TOPICS IN REGULAR LANGUAGES
9.1 DFA Minimization
9.2 Two-Way Finite Automata
9.3 Finite-State Transducers
9.4 Advanced Regular Expressions
CHAPTER 10: GRAMMARS
10.1 A Grammar Example for English
10.2 The 4-Tuple
10.3 The Language Generated by a Grammar
10.4 Every Regular Language Has a Grammar
10.5 Right-Linear Grammars
10.6 Every Right-Linear Grammar Generates a Regular Language
CHAPTER 11: NON-REGULAR LANGUAGES
11.1 The Language {anbn}
11.2 The Languages {xxR}
11.3 Pumping
11.4 Pumping-Lemma Proofs
11.5 Strategies
11.6 Pumping And Finite Languages
CHAPTER 12: CONTEXT-FREE LANGUAGES
12.1 Context-Free Grammars and Languages
12.2 Writing CFGs
12.3 CFG Applications: BNF
12.4 Parse Trees
12.5 Ambiguity
12.6 EBNF
CHAPTER 13: STACK MACHINES
13.1 Stack Machine Basics
13.2 A Stack Machine For {anbn}
13.3 A Stack Machine For {xxR}
13.4 Stack Machines, Formally Defined
13.5 Example: Equal Counts
13.6 Example: A Regular Language
13.7 A Stack Machine For Every CFG
13.8 A CFG For Every Stack Machine
CHAPTER 14: THE CONTEXT-FREE FRONTIER
14.1 Pumping Parse Trees
14.2 The Language {anbncn}
14.3 Closure Properties For CFLs
14.4 Non-Closure Properties
14.5 A Pumping Lemma
14.6 Pumping-Lemma Proofs
14.7 The Languages {xx}
CHAPTER 15: STACK MACHINE APPLICATIONS
15.1 Top-Down Parsing
15.2 Recursive Descent Parsing
15.3 Bottom-Up Parsing
15.4 PDAs, DPDAs, and DCFLs
Press Spacebar to continue
CHAPTER 16: TURING MACHINES
16.1 Turing Machine Basics
16.2 Simple TMs
16.3 A TM For {anbncn}
16.4 The 7-Tuple
16.5 The Languages Defined By A TM
16.6 To Halt Or Not To Halt
16.7 A TM For {xcx | x ∈ {a,b}* }
16.8 Three Tapes
16.9 Simulating DFAs
16.10 Simulating Other Automata
CHAPTER 17: COMPUTABILITY
17.1 Turing-Computable Functions
17.2 TM Composition
17.3 TM Arithmetic
17.4 TM Random Access
17.5 Functions And Languages
17.6 The Church-Turing Thesis
17.7 TM and Java Are Interconvertible
17.8 Infinite Models, Finite Machines
CHAPTER 18: UNCOMPUTABILITY
18.1 Decision and Recognition Methods
18.2 The Language Lu
18.3 The Halting Problems
18.4 Reductions Proving a Language Is Recursive
18.5 Reductions Proving a Language Is Not Recursive
18.8 Recursively Enumerable Languages
18.9 Languages That Are Not RE
18.10 Language Classifications Revisited
18.11 Grammars And Computability
18.13 Mathematical Uncomputabilities
Press Spacebar to continue
CHAPTER 19: COST MODELS
19.1 Asymptotic Notation
19.2 Properties of Asymptotics
19.3 Common Asymptotic Functions
19.4 A TM Cost Model
19.5 A Java Cost Model
CHAPTER 20: DETERMINISTIC COMPLEXITY CLASSES
20.1 Time Complexity Classes
20.2 Polynomial Time
20.3 Exponential Time
20.4 Space Complexity Classes
20.5 Higher Complexity Classes
CHAPTER 21: NONDETERMINISTIC COMPLEXITY CLASSES
21.1 Verification Methods
21.2 NP, NP-Hard, And NP-Complete
21.3 A Tour of Six Decision Problems
21.4 The Wider World of NP-Complete Problems
21.5 Nondeterministic Turing Machines
21.6 The Million Dollar Question
Press Spacebar to continue