1. Introduction
1.1 Formal Languages
Example 1–1
Example 1–2
1.2 Finite State Machines
Example 1–3
Example 1–4
Example 1–5
Example 1–6
Example 1–7
Paper Exercises
Chapter Summary
I Regular Languages
2. Finite Automata
Where Are We?
Chapter Objectives
2.1 Deterministic Finite Automata
Example 2–1
Example 2–2
Example 2–3
Example 2–4
Example 2–5
Example 2–6
Example 2–7
Example 2–8
Paper Exercises
Programming Exercise
Exercise 1
2.2 Non-Deterministic Finite Automata
Example 2–9
Example 2–10
Example 2–11
Example 2–12
Example 2–13
Equivalence of NFAs and DFAs
Example 2–14
NFAs and Complements
Example 2–15
Example 2–16
Paper Exercises
Exercise 2
2.3 Minimal Automata
Example 2–17
Example 2–18
Example 2–19
Example 2–20
Paper Exercises
Exercise 3
2.4 Machines with Output
Example 2–1
Example 2–22
Example 2–23
Example 2–24
Computer Arithmetic
Example 2–25
Example 2–26
Example 2–27
Lexical Analysis
Example 2–28
Example 2–29
Minimal Mealy Machines
Example 2–30
Paper Exercises
Programming Exercises
Chapter Summary
Exercise 4
Quiz 1
1 attempt allowed
3. Regular Expressions and Grammars
Where Are We?
Chapter Objectives
3.1 Regular Expressions
Paper Exercises
3.2 Equivalence of Regular Expressions and Regular Languages
From Regular Expression to NFA
From NFA to Regular Expression
Example 3–1
Example 3–2
Paper Exercises
3.3 Regular Grammars
Example 3–3
Left-Linear Grammars
Example 3–4
Example 3–5
Example 3–6
Paper Exercises
Chapter Summary
Exercise 5
Quiz 2
1 attempt allowed
4. Properties of Regular Languages
Where Are We?
Chapter Objectives
4.1 Closure Properties
Example 4–1
Computing Set Operations
Example 4–2
Example 4–3
Paper Exercises
Exercise 6
4.2 Decision Algorithms
Example 4–4
Example 4–5
Example 4–6
Paper Exercises
4.3 Infinite Regular Languages and a “Pumping Theorem”
A “Pumping Theorem” for Infinite Regular Languages
Example 4–7
The Pumping Theorem for Regular Languages
Example 4–8
Example 4–9
Example 4–10
Example 4–11
Example 4–12
Example 4–13
Example 4–14
Using Closure Properties to Show Non-Regularity
Example 4–15
Paper Exercises
Chapter Summary
Exercise 7
Quiz 3
1 attempt allowed
II Context-Free Languages
5. Pushdown Automata
Where Are We?
Chapter Objectives
5.1 Adding a Stack to Finite Automata
Example 5–1
Example 5–2
Example 5–3
Example 5–4
Example 5–5
Example 5–6
Example 5–7
Paper Exercises
Exercise 8
5.2 Pushdown Automata and Determinism
Example 5–8
Paper Exercise
Chapter Summary
Quiz 4
1 attempt allowed
6. Context-Free Grammars
Where Are We?
Chapter Objectives
6.1 Context-Free Grammars and Derivations
Example 6–1
Example 6–2
Example 6–3
Example 6–4
Example 6–5
Example 6–6
Example 6–7
Example 6–8
Example 6–9
Simplifying Grammars
Example 6–10
Example 6–11
Paper Exercises
Programming Exercise
Exercise 9
6.2 Derivation Trees and Ambiguous Grammars
Example 6–12
Operator Precedence
Operator Associativity
Example 6–13
Expression Trees
Paper Exercises
Exercise 10
6.3 Equivalence of PDAs and CFGs
From CFG to PDA
Example 6–14
From PDA to CFG (Special Case)
Example 6–15
From PDA to CFG (General Case)
Example 6–16
Example 6–17
Example 6–18
Paper Exercises
Chapter Summary
Exercise 11
Quiz 5
1 attempt allowed
7. Properties of Context-Free Languages
Where Are We?
Chapter Objectives
7.1 Chomsky Normal Form
Removing Lambda
Example 7–1
Removing Unit Productions
Example 7–2
Chomsky Normal Form Rules
Example 7–3
Example 7–4
Paper Exercises
Exercise 12
7.2 Closure Properties
Closure Properties of DCFLs
Paper Exercises
Exercise 13
7.3 Decision Algorithms
Stage 1
Stage 2
Stage 3
Stage 4
Diagonal (Stage) 1
Diagonal (Stage) 2
Diagonal 3
Diagonal 4
Example 7–5
Is a CFL Empty or Infinite?
Example 7–6
Example 7–7
Paper Exercises
Exercise 14
7.4 Infinite CFLs and Another Pumping Theorem
The Pumping Theorem for Context Free Languages
Example 7–8
Example 7–9
Example 7–10
Example 7–11
Example 7–12
Paper Exercises
Chapter Summary
Exercise 15
Quiz 6
1 attempt allowed
III Recursively Enumerable Languages
8. Turing Machines
Where Are We?
Chapter Objectives
8.1 Prelude
Queue Machines
Exercise
8.2 The Standard Turing Machine
Example 8–1
Example 8–2
Example 8–3
Example 8–4
Example 8–5
Subroutines
Example 8–6
Halting
Paper Exercises
Exercise 16
8.3 Variations on Turing Machines
The Universal Turing Machine
Non-Deterministic TM = Deterministic TM
Programming Exercise
Chapter Summary
Exercise 17
Quiz 7
1 attempt allowed
9. The Landscape of Formal Languages
Where Are We?
Chapter Objectives
9.1 Recursively Enumerable Languages
A Non-Recursive, RE Language
Context-Sensitive Languages
Properties of Recursively Enumerable Languages
Paper Exercises
9.2 Unrestricted Grammars
Example 9–1
Example 9–2
Example 9–3
Example 9–4
Context-Sensitive Grammars
Equivalence of Unrestricted Grammars and Turing Machines
Example 9–5
Example 9–6
Paper Exercises
Exercise 18
9.3 The Chomsky Hierarchy
Countable Sets
Uncountable Sets
Chapter Summary
Exercise 19
Quiz 8
1 attempt allowed
10. Computability
Chapter Objectives
10.1 The Halting Problem
Exercise 20
10.2 Reductions and Undecidability
Example 10–1
Example 10–2
Example 10–3
Paper Exercises
Chapter Summary
Exercise 21
Quiz 9
1 attempt allowed
Foundations of Computing
An Accessible Introduction to Formal Languages
Foundations of Computing
An Accessible Introduction to Formal Languages
An accessible, practical approach to formal languages with an introduction to computability.
The instructor is letting you choose the price you pay for this course!
The instructor is letting you choose the price you pay for this course!
An accessible, practical approach to formal languages with an introduction to computability.
About
About the Course
The course is based on a textbook for upper-division Computer Science majors covering formal languages and automata with an introduction to computability. Intended to give CS majors a solid foundation in the Theory of Computation without being overly formal mathematically, while retaining the rigor of the material. It has been classroom tested since 2016 with good success.
This course includes nearly three hours of exclusive video interviews with the author, covering questions related to each of the six lessons included in the course.
Price
Course Price
Minimum price
$129.00
$179.00
You pay
$179.00Author earns
$143.20Instructor
About the Instructor
Charles D. Allison
Professional software developer for 20 years until 2001. Professor of Computer Science at Utah Valley University 2001–2022. Former contributing member of the C++ Standards Committee and Senior Editor of the C/C++ Users Journal. Author of C & C++ Code Capsules (Prentice-Hall, 1998) and co-author of Thinking in C++, Volume 2 (Prentice-Hall, 2004, with Bruce Eckel).
Material
Course Material
The Leanpub 60 Day 100% Happiness Guarantee
Within 60 days of purchase you can get a 100% refund on any Leanpub purchase, in two clicks.
Now, this is technically risky for us, since you'll have the book or course files either way. But we're so confident in our products and services, and in our authors and readers, that we're happy to offer a full money back guarantee for everything we sell.
You can only find out how good something is by trying it, and because of our 100% money back guarantee there's literally no risk to do so!
So, there's no reason not to click the Add to Cart button, is there?
See full terms...
Earn $8 on a $10 Purchase, and $16 on a $20 Purchase
We pay 80% royalties on purchases of $7.99 or more, and 80% royalties minus a 50 cent flat fee on purchases between $0.99 and $7.98. You earn $8 on a $10 sale, and $16 on a $20 sale. So, if we sell 5000 non-refunded copies of your book for $20, you'll earn $80,000.
(Yes, some authors have already earned much more than that on Leanpub.)
In fact, authors have earned over $14 million writing, publishing and selling on Leanpub.
Learn more about writing on Leanpub
Free Updates. DRM Free.
If you buy a Leanpub book, you get free updates for as long as the author updates the book! Many authors use Leanpub to publish their books in-progress, while they are writing them. All readers get free updates, regardless of when they bought the book or how much they paid (including free).
Most Leanpub books are available in PDF (for computers) and EPUB (for phones, tablets and Kindle). The formats that a book includes are shown at the top right corner of this page.
Finally, Leanpub books don't have any DRM copy-protection nonsense, so you can easily read them on any supported device.
Learn more about Leanpub's ebook formats and where to read them
Write and Publish on Leanpub
You can use Leanpub to easily write, publish and sell in-progress and completed ebooks and online courses!
Leanpub is a powerful platform for serious authors, combining a simple, elegant writing and publishing workflow with a store focused on selling in-progress ebooks.
Leanpub is a magical typewriter for authors: just write in plain text, and to publish your ebook, just click a button. (Or, if you are producing your ebook your own way, you can even upload your own PDF and/or EPUB files and then publish with one click!) It really is that easy.