COT 5310: Theory of Automata and Formal Languages

Fall Semester, 2019

Purpose of the course:

This course is designed to complement the material learned in COT 4420, Theory of Computation, to create a well-rounded and rigorous treatment of topics in the Theory of Computation.  The undergraduate class dealt with formal languages and automata, while this course deals with computability theory.  Classic computability theory is defined by what abstract machines, i.e. Turing and Post machines, are capable of computing.  In this course we develop this same material using a very simple programming language first developed by Martin Davis.  The approach is very rigorous, yet the use of a programming language is much more intuitive than the classical approach using Turing machines.  Students are expected to master many sophisticated concepts, and will be asked to show their mastery with problems and in-class tests that will include technical proofs.  Material covered in the course will include:

Course Objectives:

Course Textbooks:

Besides the required textbook for this course, but here are a list of several books that cover important material for this course.  The books are listed in the order of relevance as determined by the instructor:

Meeting Place:

Love 103

Meeting Time:

8:00AM to 9:15AM: Tuesdays and Thursdays

Office Hours:

I am either in my 498 DSL office or my Love 207 office and my office hours are 9:30-10:30AM on Mondays and Wednesday
Prerequisites for the course:

Students in this course should have taken COT 4020, Theory of Computation, or its equivalent.  Students should know the basic theory concerning regular languages, context-free languages, and the basics of Turing machines.

Course Notes:

The notes for the course can be found here.


Michael Mascagni, Ph.D.
Professor of Computer Science
Professor of Mathematics (Courtesy)
Professor of Scientific Computing (Courtesy)
Faculty in the Graduate Program in Molecular Biophysics
Florida State University
Tallahassee, FL  32306-4530
Office: Dirac Science Library 498/Love 207
Telephone: +1.850.644.3290

For the curious, here are links to a brief biography of the Professor, and the Professor's home page.

Warning and Encouragement:

The students are warned that by taking this course they are implicitly submitting themselves in the role of instructional "Guinea Pigs."  As such, your constant input is not only permitted, but strongly encouraged.  Feel free to speak up in class, to visit me in my office with your opinions and criticisms, or to e-mail me with ideas on how to improve this class.

Grading Policy:

The course will  have an in-class mid-term exam, a take home final and a set of  three assignments.

Assigments@10% each 30%
In-class Midterm Exam 40%
Final Exam 30%
Total 100%

The grading scale is the standard scale with +/- being 3 percent. 

100%-90% A
89%-80% B
79%-70% C
69%-60% D
<60% F

Academic Honor Code:

Students are expected to uphold the Academic Honor Code published in The Florida State University Bulletin and the Student Handbook.  The Academic Honor System of The Florida State University is based on the premise that each student has the responsibility (1) to uphold the highest standards of academic integrity in the student's own work, (2) to refuse to tolerate violations of academic integrity in the university community, and (3) to foster a high sense of integrity and social responsibility on the part of the university community.

Please see the following web site for a complete explanation of the Academic Honor Code.

Americans with Disabilities Act:

Students with disabilities needing academic accommodation should: (1) register with and provide documentation to the Student Disability Resource Center; (2) bring a letter to the instructor indicating the need for accommodation and what type. This should be done during the first week of class.

For more information about services available to FSU students with disabilities, contact the

Student Disability Resource Center
Dean of Students Department
08 Kellum Hall
Florida State University
Tallahassee, FL 32306-4400
+1.850.644.9566 (voice)
+1.850.644.8504 (TDD)

(This syllabus and other class materials are available in alternative format upon request.)