CSE4083/CSE5210: Formal Languages and Automata (Fall 2020)

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 1pm to 1:50pm Mondays, Wednesday, and Fridays in SKU, room 120. Find the zoom meetings on Canvas.

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

This course concerns one of several core areas in computer science: models of computation, computability theory, and complexity theory. One of the main subjects, syntax, is an important topic in several central fields in computer science: programming languages, compilers, and formal languages.
relationships of formal languages different perspectives of formal languages

Why study formal languages and Automata?

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 and Susan Rodgers.
Introduction to Formal Languages, and Automata, seventh edition.
Sudbury, Massachusetts: Jones & Bartlett, 2022.
ISBN-13: 978-1284231601
book cover
Linz Peter Linz.
Introduction to Formal Languages, and Automata, sixth edition.
Sudbury, Massachusetts: Jones & Bartlett, 2017.
ISBN-13: 978-1-284077247
book cover
It is the indispensable exposition of the material in the class. No topics will be added that are not in the textbook. The book has numerous worked examples and solutions to problems. It is, in my opinion, the easiest to follow. It will not be possible to cover all the topics in the textbook.

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
book cover
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
book cover
Harrison Michael A. Harrison.
Introduction to Formal Language Theory.
1978.
book cover
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.
book cover
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.
book cover
Goddard Wayne Goddard.
Introducing the Theory of Computation.
DOI ISBN: 9780763741256.
Sudbury, Massachusetts: Jones & Bartlett, 2008.
book cover
Singh Arindama Singh.
Elements of Computation Theory.
DOI ISBN: 978-1-84882-497-3.
London: Springer, 2009.
book cover

The subject can be categorized along two major axes: expressivity and mechanism. For each of the two books we display a chart of the chapters and sections categorized this way.
Road map of chapters in Linz, 6th edition
mathautomatagrammarexpressionsproperties
Introduction1.11.2
Regular23.33.1, 3.24
Context-Free75, 6algebra8
Context-Sensitive10.511.3
Recursive enumerable9, 1011.2λ
Chapter 13: Other Models of Computation
Chapter 14: An Overview of Complexity Theory

Road map of chapters in Hopcroft, Motwani, and Ullman, 3rd edition
mathautomatagrammarexpressionsproperties
Introduction1
Regular2Ex 5.1.434
Context-Free65algebra7
Context-SensitiveLBACSG
Recursive enumerable8λ
Chapter 10: Intractable Problems
Chapter 11: Additional Classes of Problems

Lecture Notes

These lecture notes do not replace the textbook, but do provide an overview.

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.

The Udacity course "Computability, Complexity & Algorithms" is a somewhat different course, but some the lectures on topics common with our class are quite good. Watch the full course at Udacity.

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

In accordance “Florida Tech Safe: Return to Learn” procedures, instructors will enforce Florida s mandatory face covering policy in all classrooms and teaching labs. All students MUST wear appropriate face coverings that cover their mouth and nose during all face-to-face course meetings. Students who fail to comply with this policy WILL BE REQUIRED to leave the classroom immediately. Students unable to comply may contact the Dean of Students Rodney Bowers for further options.

Grading and assignments

Nearly every week there is a practice problem set. Completetion of some exercises and participation in class will count for 10 percent of your grade. The one midterm will be 40 percent and the final 50 percent.

Practice Problem Sets

Week 1
Linz, Chapter 1: Preliminaries
Week 2
Linz, Chapter 2: Finite Automata
Week 3
Linz, Chapter 2: Finite Automata
Week 4
Linz, Chapter 3: Regular Expressions
Week 5
Linz, Chapter 4: Properties of Regular Languages
Week 6
Linz, Chapter 4: Properties of Regular Languages,
Week 7
Linz, Chapter 5: Context-Free Languages,
Week 8
Linz, Chapter 6: Simplification of Context-Free Grammars and Normal Forms
Week 9
Linz, Chapter 7: Pushdown Automata
Week 10
Linz, Chapter 8: Properties of Context-Free Languages
Week 11
Linz, Chapter 9: Turing Machines
Week 12
Linz, Chapter 10: Other Models of Turing Machines
Week 13
Linz, Chapter 11: A Hierarchy of Formal Languages and Automata, Chapter 12: Limits of Algorithmic Computations

Miscellaneous Videos

Latex