Notes on Models of Computation

Chapter Index

**H. Conrad Cunningham**

**14 April 2022**

Copyright (C) 2015, 2022, H. Conrad Cunningham

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

**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.

[1]

Peter Linz. 2011. *Formal languages and
automata* (Fifth ed.). Jones & Bartlett, Burlington,
Massachusetts, USA.