CSCI 4333 - Theory of Computation

(Fall 2023: CRN 80547)

Printable Course Syllabus

Byron Jeff

Phone: 678-466-4411 (Please leave a voicemail)
Office: UC 338
Office hours (In person, Teams or E-mail):
    MW 1:00 - 2:00 PM, 3:30 - 4:30 PM, T 2:00 - 3:30 PM, or by appointment via Teams/E-mail

Note: the syllabus and schedule are subject to change.

Course Description (3-0-3)

Theory of Computation: This course is a study of the main areas of theoretical computer science and their hierarchical interconnections. Basic results relating to formal models of computation are studied, with emphasis on grammars and languages, finite automata, Turning machines, and computational complexity.

Course Objectives:

Students are expected to obtain a developing level of mastery in computer science. Students will demonstrate an emerging level of knowledge of a broad range of fundamental computer science concepts and topics. Students should show potential to perform independently and should exhibit a high level of reasoning, critical thinking and problem solving skills. Course objectives are listed for each CS program outcome: At the end of the course the student should be able to:
  1. Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines
  2. Design finite automata corresponding to given regular sets, and describe the regular set associated to a given finite automaton. Do the same with pushdown automata and context-free languages, and with Turing machines and recursively enumerable sets
  3. Comprehend and apply a number of algorithms such as: the subset construction to transform a indeterministic finite automaton into a deterministic one; the DFA state minimization to minimize the number of states in a deterministic finite automaton; and the conversion algorithms from regular expressions to finite automata and vice versa
  4. 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)
  5. 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
  6. Apply algorithms to transform context-free grammars into normal forms such as the Chomsky and Greibach normal forms
  7. Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction

Program Outcomes:

The CS curriculum is built on six core program outcomes. Successful completion of this course will contribute to the following subset of these outcomes. Graduates will demonstrate a Mastery Level for the following outcomes: 1.Solve complex and significant problems with professional skill by formulating efficient and effective algorithmic solutions to a wide variety of sophisticated problems normally encountered in computing and in academe,

3.Apply core concepts in computer science,

6.Demonstrate an ability to acquire, interpret, and communicate results orally or in writing.


CSCI 3333: Programming Languages

Meeting Times

Day of weekTimesCRNRoom
MW 2:10-3:25 PM 80547UC 322

Class Email: (80547 MW afternoon class)


Introduction to Languages and the Theory of Computation, 4/e (4th Edition) by Martin, McGraw Hill


You will have numerous opportunities to practice and demonstrate mastery of the materials covered in this course. It is up to you to keep current on all readings and assignments (including in-class announcements). *If you fall behind, you will most assuredly fail this course!*

Grading will be based upon the following scale:

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

Assignment weights are as follows:

AssignmentPortion of Grade
Final 30%
Three Monthly Tests 39% (12% for each of 3 tests given approximately once a month)
Review Quizzes 12%
Project Portfolio (see details below) 12%
D2L online Discussions (see details below) 7%

The final for this class is comprehensive. In addition the grade on the final can be used to redeem one *(and only one)* monthly test grade. So if your grade on the final is higher than your lowest monthly test grade, then that monthly test grade will be replaced with the grade from the final. This policy is designed to give a student the chance to improve one poor monthly test showing.

Partial credit may be given.

Course Topics

The list of course topics below will be presented in the order listed below. The listed exams are inserted following the likely coverage of the material that the exam will cover. Be aware that in class adjustments of both the material and the exam coverage may be made. Any in class adjustments superceeds the outline listed here. Exact test dates will be announced a minimum of one week before the actual exam.

COVID Health and Safety Statement

Clayton State University is committed to providing and promoting a healthy and safe learning environment. Anyone who is feeling ill should refrain from coming to campus and should consult the symptoms related to COVID to determine if a visit to a physician or clinic is necessary. Any faculty, staff or student who has tested positive for COVID or has been potentially exposed to someone with COVID should report their case using the COVID Reporting Form before coming to campus. Once the report is submitted you will receive further instructions via your CSU email. Individuals on campus who choose to wear a face mask are free to do so at any time.

Project Portfolio

Please read carefully!

A comprehensive student generated project portfolio must be submitted by each student on the specified date near the end of the semester. The portfolio consists of a number of required project elements coupled with additional project elements selected by the student. The portfolio will serve as the single grading instrument for the project portion of the course. The portfolio will be graded on the following elements:

Each element of the project portfolio will have a milestone/feedback deadline during the semester. Project elements that are substantively complete and correct (i.e. not perfect but mostly done) and turned in by the milestone/feedback deadline will receive feedback that the student may use to improve their project for the portfolio. However, any project element that is not submitted for feedback by the given deadline, or is not substantively complete/correct at that deadline will not receive credit for meeting the milestone/feedback deadline nor feedback incorporation element for that project element.

Active Feedback System

Soliciting and incorporating feedback is an essential element for success in the learning and development of technological systems. In order to encourage active student participation in the feedback process, this course implements an active feedback points system. The system is governed by the following rules:

Pictures/Recordings of Course Content in Lecture

The practice of students taking pictures of course content in class has become so prevalent that it now rises to the level of disruptive class behavior. While the instructor understands that students are attempting to reorganize course content such that it's easier for them to access offline, it triggers two levels of distraction in the classroom:

  1. The practice distracts the instructor who is in the process of trying to explain the course content.

  2. The practice distracts the student attempting to capture the image because that student is no longer focused on the course content, but with the process of trying to capture the image.

Because of these issues, this practice will be limited during lecture in the course in the following two ways:

  1. For course content that the student has access to, such as course slides, or project/discussion pages posted to D2L, students may only take pictures of that content from their own screens and not the projected lecture screen for the class.

  2. For handwritten course content on boards, or annotated slides, students may take pictures of the content off the board or projector when access is granted by the instructor.

Students are encouraged to share their notated board shots in the class discussion forum named "Class Notes and Board Shots" which can be a shortcut to each individual student needing to take their own shot of an image that has been shared.

Attendance Policy

Your active participation in class is expected. Class attendance is expected because it's much easier to learn if you're participating in class and asking questions about things that confuse you.

Late Work Policy

Late work delays both the learning process and the feedback process. Project elements needs to be turned in a timely fashion. D2L assignment submissions for project elements will be closed 24 hours after the feedback deadline.

The instructor may waive late penalties if techical problems to homework submission occurs. In the event of technical difficulties:


Academic Misconduct

Any student is found obtaining or granting inappropriate help in this course on any in-class graded assignment (test, quiz, exam) will subject to acadmic discipline. The offense will go on permanent record with the university. If this is not the student's first academic misconduct offense at CSU, he will be recommended for expulsion from the university. This is in full accord with CSU's policy, and we encourage you to read and review the university's policy in your student handbook.

So it is permissible to do group work or work with a tutor or other instructors on outside work in this course that is to be turned in for a grade. However, remember that the objective is to gain understanding of the problem solving process and apply that understanding. Note that the majority of the course grade is done via an in-class assessment, which each student must do on their own work without assistance.

Academic discipline can range from a zero for the in-class assessment in question to expulusion from the University depending on the circumstances.

All alleged instances of acadmic misconduct will be referred to the Office of Student Affairs.

Personal/Emotional Concerns

A range of issues can cause barriers to learning, such as stress, strained relationships, feeling down, difficulty concentrating, and lack of motivation. During the semester, if you find that life stressors are interfering with your academic or personal success, consider contacting Counseling and Psychological Services (CAPS.) All students are eligible for counseling services at no charge. CAPS is located in Edgewater Hall, Room 245. You can reach them by phone at 678-466-5406 or email to request an appointment at Students can reach the 24/7 Support Line by calling 833-855-0084.

Hardship Withdrawal

Students who experience an unexpected event or circumstance beyond their control that directly interferes with their ability to continue to make satisfactory progress in classes, such as serious illnesses or unexpected major life events, may petition the Dean of their major for a hardship withdrawal from all classes. In order to be considered for a hardship withdrawal, the student must have been passing all courses at the time that the emergency or other hardship arose and notify his or her instructors or other University officials about the hardship situation as soon as possible after it arose (per University and BOR policy, passing is defined as a grade of D or above). Hardship requests that are not filed in a timely manner are subject to denial even if the student was passing and the hardship was legitimate. Students who attend any classes through the end of a term and complete all course requirements (i.e. final project or exam) are not eligible for hardship withdrawal. If you have taken a final exam in any of your courses, you may not request a hardship withdrawal. For more information go to:

ITP Choice Information

Beginning Fall Semester 2001, all students at CCSU are required to state that they have on-demand access to a notebook computer that meets the recommended hardware/software specifications that have been established by Clayton State faculty. Academic penalties may be incurred for not meeting this requirement. See for more information.

Library Syllabus Statement

The Clayton State Library provides services and resources to support your academic success not only in this course, but throughout your career at Clayton State and beyond. Each academic department has an assigned personal librarian who is knowledgeable about resources in that subject area. You are encouraged to contact your department's personal librarian to schedule a one-on-one consultation for help with any research assignments. You can also receive personalized research support through chat, email, phone, text, or in-person any time the library is open. You may also access online research guides, LibGuides, created by Clayton State Librarians directing you to the best resources in selected subject areas. All the information about these and other resources is available on the library's homepage. For further questions, contact the library using the information below:

Call: (678) 466-4346


Research Support:



Find your personal librarian:

Clayton State Library YouTube:

Disruption of the Learning Environment

Behavior which disrupts the teaching-learning process during class activities will not be tolerated. While a variety of behaviors can be disruptive in a classroom setting, more serious examples include belligerent, abusive, profane, and/or threatening behavior toward the instructor and/or other students in the class. A student who fails to respond to reasonable faculty direction regarding classroom behavior and/or behavior while participating in classroom activities may be dismissed from the class. A student who is dismissed from the class is entitled to due process and will be afforded such rights as soon as possible following dismissal, in collaboration with the Office of Community Standards. If found in violation, a student may be administratively withdrawn and may receive a grade of WF. More detailed examples of disruptive behavior are provided in the Code of Conduct and Disciplinary Procedures sections of the Clayton State University Academic Catalog and Student Handbook.

Weapons on Campus

Clayton State University is committed to providing a safe environment for our students, faculty, staff, and visitors. Information on laws and policies regulating weapons on campus are available at

Disability Services

Students with disabilities who require reasonable accommodations need to register with Disability Services (DS) in order to obtain their accommodations. You can contact them at 678-466-5445 or E-mail at .