A printable PDF is also available.
CSC 452 – Fall 2024 – Syllabus
Instructor: Stephen R. Tate (Steve)
Lectures: Mon/Wed 3:30-4:45, Petty 224
Office: Petty 157
Office Hours: Mon/Wed 1:30-3: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.f24/
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) [5 classes]
Context-Free Languages (Chapter 2) [5 classes]
The Church-Turing Thesis (Chapter 3) [2 classes]
Decidability (Chapter 4) [2 classes]
Reducability (Chapter 5) [2 classes]
Time Complexity (Chapter 7) [3 classes]
Basic Space Complexity (Sections 8.1–8.2) [1 class]
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: For practice and to demonstrate abilities, students will be given 6 assignments over the course of the semester (approximately every two weeks, adjusted to exclude exam weeks). Assignments will consist mostly of written problems but may include a few programming problems as well. Solutions for written problems 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. Do not use a standard word processor such as Word or LibreOffice unless you properly write mathematics using the equation editor capabilities. Points will be taken off for sloppy presentation, which includes improperly formatted mathematics. If programming problems are assigned, they can be completed in Java, C++, or Python; other languages may be used if pre-approved by the instructor.
Exams: There will be two mid-term exams and one final exam. Tentative dates for each exam are provided on the class web site schedule.
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:
| Grade Weights | |
|---|---|
| Assignments | 35% |
| Mid-term Exam 1 | 20% |
| Mid-term Exam 2 | 20% |
| Final Exam | 25% |
| 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- |
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/
Assignments in this class are for individual work, unless explicitly stated otherwise. Note that “individual work” means work created by you, reported in your own words, and use of AI tools like ChatGPT is not allowed. General concepts and material covered in the class may be discussed with other students or in study groups, but specific assigned problems should not be discussed and all submitted work should be entirely your own. For example, if a homework includes a problem to convert an NFA to a DFA, you may discuss the general conversion technique, and you may work through non-assigned conversion problems together, but you may not discuss the assigned NFA. Collaboration on, or sharing of, solutions to assigned problems, whether in person or via electronic communication tools such as Discord, is an integrity violation. If you use external references (including web sites, books, etc.) in preparing your solutions, you should clearly mark the part(s) of your solution influenced by these references and provide clear citations to the source of information you are using. Doing a Google search for solutions to assigned problems is a violation of academic integrity, whether or not you use what you find in your answer. Sharing your own work is a serious violation of academic integrity, and if homework is copied then both the person who actually did the work and the person who copied it will be punished. Any incidents of academic dishonesty will be handled strictly, resulting in either a zero on the assignment or an F in the class, depending on the severity of the incident. 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 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-quizes 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. Assignments may be turned in one day late (up to 11:59PM the following day) for a 15% penalty, or two days late for a 30% penalty. No assignment will be accepted more than 48 hours late for any reason. 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 timeframe to allow students to adjust as needed.