School of Computing
fit wordmark

CSE4083: Formal Languages and Automata (Spring 2017)

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 noon to 12:50am Mondays, Wednesday, and Fridays in the Crawford Building, room 402.

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

relationships of formal languages different perspectives of formal languages

Why study formal languages and Automata?

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
book cover
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
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.
ISBN: .
book cover
Sudkamp Thomas A. Sudkamp.
Languages and Machines: An introduction to the Theory of Computer Science.
Boston, Massachusetts: Pearson/Addison-Wesley Education, 2006.
ISBN-13: 9780321322210.
book cover
Drobot Vladimir Drobot.
Formal Languages and Automata Theory.
New York, New York: Computer Scence Press, 1989.
ISBN: 0-7167-8186-7

Summary of Closure Properties

Summary of Chomsky Hierarchy

Grading and assignments

Students are expected to do 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.

Calendar and Important Dates

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

Monday, 9 Jan 2017first lecture
Monday, 16 January 2017MLK day, no classes
Monday, 16 January 2017HW #1 due
Friday, 27 January 2017HW #2 due
Friday, 3 February 2017HW #3 due
Monday, 6 February 2017HW #4 due
Monday, 20 February 2017Presidents' day, no classes
Friday, 24 February 2017mid-term exam
topics
Tuesday, 2 May 20171-3pm, 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

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

Automata from History