Notes on Models of Computation
Chapter Index
H. Conrad Cunningham
14 April 2022
Browser Advisory: The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of April 2022 is a recent version of Firefox from Mozilla.
These notes were written primarily to accompany my use of the textbook [1]:
Peter Linz. An Introduction to Formal Languages and Automata, Fifth Edition, Jones and Bartlett Learning, 2011.
The notes refer to chapters, sections, examples, and figures in the textbook. We wrote most of these lecture notes in Pandoc’s Markdown markup language using embedded LaTeX for mathematical notation. Using the Pandoc tool, we then converted them to HTML and LaTeX/PDF.
The HTML notes linked below contain embedded MathML. For best results, use an up-to-date FireFox browser or some other browser that renders MathML effectively.
Linz Chapter 1: Introduction to the Theory of Computation
Linz Chapter 2: Finite Automata
Linz Chapter 3: Regular Languages and Regular Grammars
Linz Chapter 4: Properties of Regular Languages
Linz Chapter 5: Context-Free Languages
OMIT Linz Chapter 6: Simplification of Context-Free Grammars and Normal Forms
Linz Chapter 7: Pushdown Automata
Linz Chapter 8: Properties of Context-Free Languages
Linz Chapter 9: Turing Machines
OMIT Linz Chapter 10: Other Models of Turing Machines
Linz Chapter 11: A Hierarchy of Formal Languages and Automata
Linz Chapter 12: Limits of Algorithmic Computation
I produced this set of notes in Fall 2015 to accompany my lectures in CSci 311, Models of Computation, at the University of Mississippi. I used the textbook [1]:
Peter Linz. An Introduction to Formal Languages and Automata, Fifth Edition, Jones and Bartlett Learning, 2011.
My teaching assistants that semester, Clay McLeod and Eli Allen, created the initial versions of the notes in Pandoc Markdown from my handwritten transparency slides from my teaching of the course in the late 1990s. I edited and expanded the initial versions to create these notes.
I retired from the full-time faculty in May 2019. As one of my post-retirement projects, I am continuing work on possible textbooks based on the course materials I had developed during my three decades as a faculty member. In January 2022, I began refining the existing content, integrating separately developed materials together, reformatting the documents, constructing a unified bibliography (e.g., using citeproc), and improving my build workflow and use of Pandoc.
I maintain this chapter as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed.