Syllabus: COT 5310 Theory of Automata and Formal Languages Fall 2024
Syllabus: COT 5310 Theory of Automata and Formal Languages Fall 2024
This course offers a comprehensive and rigorous exploration of topics in the Theory of Computation. It delves into classical computability theory, traditionally defined by the capabilities of abstract machines such as Turing and Post machines. However, in this course, we approach these concepts through a more intuitive method by using a simple programming language developed by Martin Davis. While maintaining a high level of rigor, this approach allows for a more accessible understanding compared to the classical methods.
This course requires knowledge of basic computer science, math, algorithms and complexity, and programming principles.
Computability, Complexity, and Languages, 2nd Edition. Author: Martin Davis, Ron Sigal, and Elaine J. Weyuker.
Time: Monday and Wednesday, 1:20PM - 2:35PM
Location: HCB 0315
Instructor: Ang Li (Email: angli at cs dot fsu dot edu)
The instructor’s office hour is Wednesday 10:00AM-11:59AM at 166 Love Building.
Teaching Assistant: Tonmoy Dey (Email: tdey@fsu.edu)
The TA's office hour is Thursday 2:30PM - 4:00PM at MCH-203B.
Course Website: https://www.causalds.org/teaching/cot-5310
Grades will be computed based on the following factors:
Homework 40%
Midterm 20%
Final 40%
Letter Grades: The letter grades will be assigned according to the following criteria, and if necessary, the grades will be curved upwards.
Mathematical Preliminaries
A Programming Language
Computable Functions
Primitive Recursive Functions
Coding the Programs
The Halting Problem
Universality
Finite Automata and Regular Languages
The Pumping Lemma and its Applications
Context-Free Grammars and Regular Grammars
There will be 5 written homework assignments throughout the semester, aligned with the corresponding material as we cover it.
Unless otherwise indicated, you may talk to other students about the homework problems but each student must hand in their own answers. You also must indicate on each homework with whom you collaborated and cite any other sources you use including Internet websites. Students should never see another student’s solution before submitting their own. Students cannot use old solution sets for this class or solution manual to the textbook under any circumstances.Homework assignments will be submitted through Canvas.
You will have a one-time exemption for a one-day late submission that you can apply to any of your assignments. This will be applied automatically at the end of the semester. The second or subsequent late assignments will be marked as 0 at the end of the semester.
Please submit your homework on time. Homework is worth full credit if submitted before the due date. After the due date, it is worth zero credit, except for the one-time exemption of a one-day late submission. No excuses will be allowed unless you provide an official doctor's note before the deadline and receive my approval.
There will be one midterm and a final exam. Both exams are open book and open notes, consisting of true-false and mathematical proof questions. You are not permitted to discuss the exams with others. Missing any exam will result in an automatic F grade.
Exams may be recorded, and any suspicious activity will be reported to the Dean's Office.
Midterm: 10/23 1:20PM - 2:35PM (Tentative) in HCB 0315
Final: 12/11 12:30PM-2:30PM in HCB 0315
All 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.
web site for a complete explanation of the Academic Honor Code.
https://fda.fsu.edu/academic-resources/academic-integrity-and-grievances/academic-honor-policy
First Day Attendance Policy: Official university policy is that any student not attending the first class meeting will be automatically dropped from the class.