School of Computing
fit wordmark

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

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, 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

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

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

Automata from History