CSE4083/CSE5210: Formal Languages and Automata (Spring 2024)

General info

Instructor

Ryan Stansifer

Office hours

Check my WWW page for up to date information, you are always welcome to send me e-mail.

Lectures

Lectures are from 2pm to 2:50pm Mondays, Wednesday, and Fridays in OEC, room 118.

Catalog Description

CSE 4083 Formal Languages and Automata Theory. Presents abstract models of computers (finite automata, pushdown automata and Turing machines) and the language classes they recognize or generate (regular, context-free and recursively enumerable). Also presents applications of these models to compiler design, algorithms and complexity theory. Prerequisite: CSE 2010.

Overview

Why study formal languages and Automata?

• Practice abstraction, modeling and mathematical correctness
• Understand the nature of syntax
• Understand the nature of computation

Prerequisites

Mathematical sophistication is required, in particular discrete math. There will be no programming projects.

Textbook

The textbook for the class is:

Linz

Peter Linz. Introduction to Formal Languages, and Automata, sixth edition. Sudbury, Massachusetts: Jones & Bartlett, 2017. ISBN-13: 978-1-284077247

Other books are similar and cover the same material. In particular the book by Hopcroft, Motwani, and Ullman (HMU) is very similar, and sometimes used as the textbook in this course.

Hopcroft

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, third edition. Boston, Massachusetts: Pearson/Addison Wesley, 2007. ISBN-13: 978-0-321-45536-3

Kozen	Dexter Campbell Kozen. Automata Theory and Computability. New York: Springer, 1997. ISBN: 978-1-4612-7309-7. DOI 10.1007/978-1-4612-1844-9
Harrison	Michael A. Harrison. Introduction to Formal Language Theory. 1978.
Martin	John C. Martin. Introduction to Languages and the Theory of Computation, fourth edition. New York, New York: McGraw-Hill, ©2011. ISBN: 9780073191461.
Sudkamp	Thomas A. Sudkamp. Languages and Machines: An introduction to the Theory of Computer Science, third edition. Boston, Massachusetts: Pearson/Addison-Wesley Education, 2006. ISBN: 9780321322210.
Floyd	Robert W. Floyd and Richard Beigel. The Language of Machines: An introduction to the Computability and Formal Languages, ? edition. New York: New York: Computer Science Press, 1994 ISBN: 9780716782667.
Goddard	Wayne Goddard. Introducing the Theory of Computation. DOI ISBN: 9780763741256. Sudbury, Massachusetts: Jones & Bartlett, 2008.
Singh	Arindama Singh. Elements of Computation Theory. DOI ISBN: 978-1-84882-497-3. London: Springer, 2009.
MacCormick	John MacCormick. What Can be Computed? A Practical Guild to the THoery of Computation.

Map of Chapters

Lecture Notes

I think the ones by Busch are the best and I have provided Panopto recordings. Ullman's follows his own book, of course, and so are not focused on the way this class is organized. Linz' notes are not as extensive at Busch's. Each grid is cross-listed with Wikipedia articles which are often quite good on these topics.

• Lecture notes by Busch following Linz.
• Lecture notes by Ullman following HMU.
• Lecture notes by Linz following Linz.

Summary of Major Theorems

Chomsky Hierarchy

As a concise reference to the entire subject, we put some of the formal languages in the levels of the Chomsky hierarchy and summarize of the closure properties of the levels.

Closure Properties

Decision Properties

Title IX Statement

Grading and assignments

Calendar and Important Dates

Syllabus

Miscellaneous Videos

• LEGO Turing machine by Aarhus University, 2009
• Halting Problem by Udi Aharoni
• Encoding a Turing Machine, Universal Turing Machine, Georgia Tech
• Proof some infinities are bigger than other infinities by Vi Hart.

Latex

• Overleaf
• Detexify
• Mathpix
• Writing Mathematics by Hart.
• Simpsons and Fermat's Last Theory