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

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 CRF, room 230.

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.
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 of the lectures are on topics common with our class, and 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

Grading and assignments

There will be two midterm exams and one final. The course grade will be based on these exams. The weights will be 30%, 30%, 60%.

Calendar and Important Dates

Consult the Florida Tech academic calendar for important dates for all classes.

Monday, 22 August 2022First lecture
Monday, 5 September 2022Labor Day (no classes)
Sunday, 18 September 2022Google Kickstart, Round F (13:00-16:00 EDT)
Friday, 23 September 2022Midterm Exam #1
Chapters 1,2,3,4
10-11 October 2022Fall Break (no classes)
Tuesday, 11 October 2022Ada Lovelace Day
Saturday, 15 Oct 2022Google Kickstart, Round G (08:00-11:00 EDT)
Sunday, 6 November 2022Daylight Savings Time ends
Fri, 4 November 2022Midterm Exam #2
Chapters 5, 6, 7, 8
Friday, 11 November 2022Vetrans Day (no classes)
Friday, 11 November 2022Google Kickstart, Round H (22:00-01:00 EST)
23-25 November 2022Thanksgiving (no classes)
Saturday, 3 December 2022Make-Up Lecture
Friday, 9 December 2022Last lecture
Tuesday, 13 December 2022Final Exam, 1-3pm

Syllabus

Week 1
Administration, Introduction. Linz, Chapter 1: Preliminaries
Week 2
Linz, Chapter 2: Finite Automata
Week 3
Linz, Chapter 3: Regular Languages
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, Section 8.1: Pumping Lemma
Week 12
Linz, Chapter 9: Turing Machines
Week 13
Linz, Chapter 10: Other Models of Turing Machines
Week 14
Linz, Chapter 11: A Hierarchy of Formal Languages and Automata, Chapter 12: Limits of Algorithmic Computations

Miscellaneous Videos

Latex