CSE4083: Formal Languages and Automata (Spring 2018)

General info

Instructor

Ryan Stansifer

Office hours

Check my WWW page for up to date information, you are welcome to send me e-mail at ryan@cs.fit.edu.

Lectures

Lectures are from 9am to 9:50am Mondays, Wednesday, and Fridays in SKU, room 116.

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, or ECE 2552, ECE 3541.

Overview

different perspectives of formal languages

Why study formal languages and Automata?

Practice abstraction, modeling and mathematical correctness
Understand the nature of syntax
Understand the nature of computation by studying models of computation

Prerequisites

Mathematical sophistication is required.

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
Hopcroft	John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation, third edition. Boston, Massachusetts: Peason/Addison Wesley, 2007. ISBN: 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. ISBN: .
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.

Chapter 5-6notes by Stansifer
Lecture notes by Ullman. Lecture videos by Ullman.
Lecture notes by Busch

Summary of Chomsky Hierarchy

Summary of Closure Properties

Grading and assignments

Students are expected make 100% on all the Gradiance homework. There will be one midterm and one final. For each student the numeric scores for the assignments and exams are recorded.

Title IX

What is Title IX?

Title IX of the Educational Amendments Act of 1972 is the federal law prohibiting discrimination based on sex under any education program and/or activity operated by an institution receiving and/or benefiting from federal financial assistance. Behaviors that can be considered “sexual discrimination” include sexual assault, sexual harassment, stalking, relationship abuse (dating violence and domestic violence), sexual misconduct, and gender discrimination. You are encouraged to report these behaviors.

Reporting

Florida Tech can better support students in trouble if we know about what is happening. Reporting also helps us to identify patterns that might arise — for example, if more than one complainant reports having been assaulted or harassed by the same individual. Florida Tech is committed to providing a safe and positive learning experience. To report a violation of sexual misconduct or gender discrimination, please contact Security at 321-674-8111. * Please note that as your professor, I am required to report any incidences to Security or to the Title IX Coordinator (321-674-8700). For confidential reporting, please contact CAPS at 321-674-8050.

Calendar and Important Dates

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

Monday, 8 Jan 2017	first lecture
Monday, 15 January 2018	Martin Luther King Jr. Day (no classes)
Monday, 19 February 2018	Presidents' day, no classes
Monday, 26 February 2018	Midterm exam Chapters 1-4
5-9 Mar 2018	Spring break (no classes)
Monday, 19 March 2018	Midterm exam Chapters 5-6
Monday, 9 April 2018	Midterm exam Chapters 7-8
Wednesday, 25 April 2018	last lecture
Thursday, 3 May 2018	8-10am, final exam

Syllabus

Week 1

Mathmatical Preliminaries

Reading assignment. Linz, Chapter 1: Preliminaries Reading assignment. HMU, Chapter 1: Preliminaries

Week 2

Finite Automata and Regular Expressions

Reading assignment. HMU, Chapter 2 and Chapter 3

Week 3

Properties of Regular Languages

Reading assignment. HMU, Chapter 4

Week 4

Context-Free Grammars and Languages

Reading assignment. HMU, Chapter 5

Week 5

Pushdown Automata

Reading assignment. HMU, Chapter 6

Week 6

Properties of Conext-Free Langauges

Reading assignment. HMU, Chapter 7

Week 7

Introduction to Turing Machines

Reading assignment. HMU, Chapter 8

Week 8

Undecidability

Reading assignment. HMU, Chapter 9

Videos

LEGO Turing machine by Aarhus University, 2009
Halting Problem by Udi Aharoni

The Udacity course "Computability, Complexity & Algorithms". Watch the full course at Udacity.

Automata from History

The Antikythera Mechanism [6 min video]
Leibniz Step Reckoner
Babbage's Difference Engine
Astronomical Clock Prague
Proof some infinites are bigger than other infinities by Vi Hart.
Seasame Street cf. Rube Goldberg
BBC News: Mechanical Turk [Requires Flash]