A printable PDF is also available.
CSC 452/652/752 – Spring 2025 – Syllabus
Instructor: Stephen R. Tate (Steve)
Lectures: Mon/Wed 2:00-3:15, Petty 303
Office: Petty 157
Office Hours: Mon/Wed 3:30-5:00, or by appointment
E-mail:
– I answer most emails within one business day – do not expect responses evenings or weekends
Class Web Page: https://home.uncg.edu/cmp/faculty/srtate/452.s25/
Catalog Description: Finite state automata and regular expressions, context-free grammars, push-down automata and their use in parsing, overview of language translation systems, models for programming language semantics, computability and undecidability.
Prerequisites: Grade of C or better in CSC 350, or permission of instructor.
Longer Description: In this class we explore the most fundamental question in computer science: What does it mean to compute something? This includes exploring issues such as processes/models that can mechanize computations, problems that can and cannot be solved with different models of computation, and fundamental limitations that restrict what problems can be solved computationally. While the focus of an algorithms class is on how fast problems can be solved by modern computers, this class digs deeper into the fundamental question of what problems are possible to solve in various computational models. The approach in this class is formal, using precise mathematical models and a significant amount of formal reasoning and mathematical proofs.
Student Learning Outcomes: Upon successful completion of this course students should be able to
Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines.
Design finite automata corresponding to given regular sets, and describe the regular set recognized by a given finite automaton. Do the same with pushdown automata and context-free languages, and with Turing machines and recursively enumerable sets.
Comprehend and apply a number of algorithms such as: the subset construction to transform a nondeterministic finite automaton into a deterministic one; the DFA state minimization algorithm to minimize the number of states in a deterministic finite automaton; and conversion algorithms from regular expressions to finite automata and vice-versa.
Understand limitations of finite automata (respectively, pushdown automata) and prove that some sets are not regular (respectively, context-free) by using the pumping lemma for regular languages (respectively, context-free languages).
Simulate CFGs by NPDAs and vice-versa, that is, convert a given context-free grammar to an equivalent nondeterministic pushdown automaton, and convert a nondeterministic pushdown automaton to an equivalent context-free grammar.
Apply algorithms to transform context-free grammars into normal forms such as the Chomsky and Greibach normal forms.
Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction.
Textbook and Readings: The required textbook is
Michael Sipser. Introduction to Theory of Computation, 3rd edition, Cengage Learning, 2013.
ISBN-13: 978-1133187790 (this is the hardcover print edition – the eBook edition in the link is much more affordable, and eBook access is included for students who participate in UNCG’s First Day Complete program).
Topics: The topics to be covered are shown below, with estimated times by each topics. For an updated week-by-week schedule, please see the class web site.
Class Overview [1 class]
Mathematical structures and proofs technique review (Chapter 0) [2 classes]
Regular Languages (Chapter 1) [4 classes]
Context-Free Languages (Sections 2.1–2.3) [3 classes]
The Church-Turing Thesis (Chapter 3) [2 classes]
Decidability (Chapter 4) [2 classes]
Reducibility (Chapter 5) [3 classes]
Time Complexity (Chapter 7) [4 classes]
Basic Space Complexity (Sections 8.1–8.3) [2 classes]
Selected Topic [1 class]
Teaching Methods and Assignments: This class will meet for two 75-minute periods per week, and class meetings will consist of a combination of lecture/presentation, discussion, and in-class exercises. Students must come to class prepared, having done all required readings, and are expected to participate in in-class activities. Class time will be heavily focused on working through problems and proofs, and there is currently no plan to use PowerPoint or any other kind of slides – problems solved in class (including proofs) will be done on the board, and students are expected to take notes. You may share your notes with others in this class, but I will not provide notes. I will follow the textbook closely, and if I cover topics outside the textbook I will always provide written material.
Assignments: There will be a short assignment almost every week (adjusted for exams), and the plan is for 11 assignments during the semester. Each assignment will be due on Sunday (except the week following Spring Break, which will be due on Tuesday), and may not be turned in late for any reason. To compensate for the number and strict deadline, the two lowest assignment grades will be dropped. Assignments will consist of 2–4 questions for practice with the material covered during the week. Assignments will be graded only for a solid attempt and not correctness. The first 10–15 minutes of the following class (typically Monday) will be used to carefully go over solutions and criteria on how to “grade” your own work, so make sure you have your solutions in class on those days to review (either on paper or electronically). These are purposely low-stakes activities that are designed so that you practice working with the material. While the assignments themselves have only a small effect on your class grade, they are vital for learning the material and performing well on exams – take them seriously!
Solutions must be submitted in Canvas as PDF documents. These documents can be either electronically prepared (LaTeX and Overleaf are highly recommended) or neatly handwritten and scanned. If you must use a phone camera rather than a scanner, you should use a “scan to PDF” app to produce a proper and readable PDF document with standard letter paper size.
Mid-term Exams: There will be two mid-term exams, and tentative dates for each exam are provided on the class web site schedule. Note that exams will be given in a standard controlled environment, and no one may leave the room during the exam for any reason. If you cannot sit for up to 90 minutes for an exam, you should see the OARS office for accommodations and an alternative exam environment with the UNCG Proctoring Lab.
Final Exam: The final exam will be held at the university-scheduled day and time, under the same exam conditions as the mid-term exams, and will be designed to be completed in under 90 minutes. The final exam will focus mostly on material that covered after the topic cut-off for the second mid-term exam; however, one question from the material covered by each mid-term exam will also be included, and in addition to counting in the final exam grade they may be used to raise previous exam grades by substituting that question’s score for the related question on the mid-term exam.
Graduate/Honors Project: Graduate students and undergraduates taking the course as a “contract honors” class will complete a project on a more advanced topic from theory of computing, going beyond the core material that is covered in the class. The project will consist of a survey paper (report) of approximately 10 pages, with several milestones and deliverables. The final report will be due on the last regular class day of the semester, which is Wednesday, April 30. Approximately half way through the semester, these students will receive more information on possible topics and report guidelines.
Evaluation and Grading: Each student work product will be graded, and the student’s final grade will be determined by assigning each category of work a weighted score according to the following distribution:
For undergraduates:
| Grade Weights | |
|---|---|
| Assignments | 20% |
| Mid-term Exam 1 | 25% |
| Mid-term Exam 2 | 25% |
| Final Exam | 30% |
| Letter Grade Assignment | ||||
|---|---|---|---|---|
| [87.5 , 89.5) = B+ | [77.5 , 79.5) = C+ | [67.5 , 69.5) = D+ | [0 , 59.5) = F | |
| [91.5 , ∞) = A | [81.5 , 87.5) = B | [71.5 , 77.5) = C | [61.5 , 67.5) = D | |
| [89.5 , 91.5) = A- | [79.5 , 81.5) = B- | [69.5 , 71.5) = C- | [59.5 , 61.5) = D- |
For graduate and honors students:
| Category | |
|---|---|
| Assignments | 18% |
| Mid-term Exam 1 | 22.5% |
| Mid-term Exam 2 | 22.5% |
| Final Exam | 27% |
| Graduate/Honors Project | 10% |
| Letter Grade Assignment | |||
|---|---|---|---|
| [87.5 , 89.5) = B+ | [77.5 , 79.5) = C+ | [0 , 71.5) = F | |
| [91.5 , ∞) = A | [81.5 , 87.5) = B | [71.5 , 77.5) = C | |
| [89.5 , 91.5) = A- | [79.5 , 81.5) = B- |
Note that sanctions for violations of academic integrity or disruptive/unprofessional behavior apply to the overall grade and do not follow this percentage breakdown.
Academic Integrity: Students are expected to be familiar with and abide by the UNCG Academic Integrity Policy, which is online at https://sa.uncg.edu/division-of-student-affairs/students/academic-resources/student-policy-handbook/academic-integrity-policy/
The assignments are for your practice, and there are no restrictions on collaboration or use of outside resources. However, unless you put in the effort to derive the solutions yourself (and not use a fellow student’s solution, or one you found online, or one that you used AI systems for) then you are only harming your own learning. This will come back to haunt you during exams.
Exams will follow regular exam rules, and any incidents of academic dishonesty will be handled strictly – up to and including an immediate F in the class. Significant incidents will be reported to the UNCG Office of Student Rights and Responsibilities. Note that the Department of Computer Science maintains records of all academic integrity incidents, and multiple violations, even in different classes or semesters, will always result in reporting to the university and serious penalties.
Attendance Policy: Attendance will not be taken in class, and is voluntary; however, all students are responsible for everything done or said in class (this can include changes in assignments, due dates, etc.). Many topics covered in this class are challenging, and the “self-grading” of assignments each Monday is vital to understanding what you are doing correctly and incorrectly. It is highly unlikely that a student who regularly misses classes will be successful in the course. If attendance becomes a problem, the instructor reserves the right to give pop-quizzes or graded in-class exercises.
The university allows for a limited number of excused absences for religious observances. Students who plan to take such an absence should notify the instructor at least two weeks in advance so that accommodations can be made (see the late work policy below). It is the student’s responsibility to obtain notes from another student if they miss class. Office hours are for answering questions about class material, and I will not re-teach a topic during office hours because you missed class.
Late Policy and Makeup Exams: Assignments are due at 11:59PM on the due date. As described above, no late assignments will be accepted for any reason, although your two lowest grades (including zeros) will be dropped. Students with planned absences, whether for university events, religious observance, or other reasons, are expected to make arrangements with the instructor to turn in assignments or take exams before the scheduled date of the assignment or test.
Exam/test dates will be announced at least two weeks in advance, and may be made up only if it was missed due to an extreme emergency and arrangements are made before the exam date. Exams may not be taken early or late due to personal travel plans.
In-class Behavior: When you are in class you should be focused on the class, and you should act in a professional and mature manner. During class there should be no eating, drinking, e-cigarettes, cellphone use, non-class related laptop use, or anything else that does not pertain to the class activities. Any distracting items may be confiscated at the discretion of the instructor. Significant violations or disruptive behavior will result in points subtracted from a student’s final grade, and possible reporting to the UNCG Office of Student Rights and Responsibilities.
ADA Statement: UNCG seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a disability must be registered with the Office of Accessibility Resources and Services located in 215 Elliott University Center: (336) 334-5440 (or on the web at https://oars.uncg.edu).
COVID-19 and Communicable Disease: We have been living with COVID for over 4 years now, and at this point it’s “just another communicable disease,” albeit one with a nasty combination of being highly contagious and very dangerous for vulnerable people (people are still dying every day). As far as this class is concerned, COVID and any other communicable disease should be treated with the following rule: be considerate of others. If you are sick, isolate until you are no longer contagious. If you must be around others and have recently been contagious, take measures to limit risks to others (maintain distance, wear a mask, etc.). The attendance policy above has information about what to do if you must miss class due to illness.
Health and Wellness: Health and well-being impact learning and academic success. Throughout your time in the university, you may experience a range of concerns that can cause barriers to your academic success. These might include illnesses, strained relationships, anxiety, high levels of stress, alcohol or drug problems, feeling down, or loss of motivation. Student Health Services and the Counseling Center can help with these or other issues you may experience. You can learn about the free, confidential mental health services available on campus by calling 336-334-5874, visiting the website at https://shs.uncg.edu/ or visiting the Anna M. Gove Student Health Center at 107 Gray Drive.
For undergraduate or graduate students in recovery from alcohol and other drug addiction, the Spartan Recovery Program (SRP) offers recovery support services. You can learn more about recovery and recovery support services by visiting https://shs.uncg.edu/spartan-recovery-program/ or reaching out to srp@uncg.edu
Elasticity Statement: It is the intention of the instructor that this syllabus and course calendar will be followed as outlined; however, as the need arises there may be adjustments to the syllabus and calendar. In such cases, the instructor will notify students in class and/or via e-mail with an updated syllabus and calendar within a reasonable time-frame to allow students to adjust as needed.