CSCI 4333 - Theory of Computation
(Fall 2023: CRN 80547)
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.
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:
- 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 associated to 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
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
- 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,
- 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
- Prove that some problems are decidable or undecidable using techniques
such as diagonalization and
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
3.Apply core concepts in computer science,
6.Demonstrate an ability
to acquire, interpret, and communicate results orally or in writing.
|Day of week||Times||CRN||Room|
|MW|| 2:10-3:25 PM || 80547||UC 322|
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
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:
|Assignment||Portion of Grade
|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.
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.
- Chapter 1: Basic Mathematical Objects
- Chapter 2: Finite Automata
- Test #1: Mid September
- Chapter 3: Regular Expressions, Nondeterminism and Kleene's Theorem
- Chapter 4: Context Free Languages
- Test #2: Mid October
- Chapter 5: Pushdown Automata
- Chapter 6: Context and Non-Context-Free Langauges
- Test #3: Monday November 20th, 2023
- Chapter 7: Turing Machines
- Final Exam: Wednesday December 6th, 2023 Time: 12:30PM
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.
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.
- Project Completeness
- Project Correctness
- Meeting milestone/feedback deadlines (feedback information below)
- Incorporating project element feedback
- Documentation of project design and development
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
- Each student begins the semester with a one feedback points balance.
- For each course element that requires feedback, the student is
responsible for actively soliciting feedback for that element.
- Students may only solicit feedback for course elements that are turned
in a timely fashion before the given due date.
- Students who solicit feedback before the deadline gain one point on
their feedback balance. Students who do not solicit feedback, or turn in
their assignment late, lose one point from their feedback balance.
- Students who have a positive feedback balance gain two
rewards. The first is that students with a positive feedback balance may
request and receive feedback via E-mail. The second is that students with a
positive reward balance at exam time earn two extra credit points on their
- Students who do not have a positive feedback balance must solicit
feedback in person during office hours. In addition students who do not
have a positive feedback balance at exam time are not eligible for extra credit points
on their exam.
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:
- The practice distracts the instructor who is in the process of trying
to explain the course content.
- 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:
- 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.
- 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.
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.
- All excused absences must be accompanied by documentation such as a
- Any excused absence for a monthly test or final must be discussed with
the instructor at least 24 hours in advance. Test absences must be
documented beforehand. Test absences that do not follow the above procedure
will result in a grade of zero that that test or final.
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
The instructor may waive late penalties if techical problems to homework
submission occurs. In the event of technical difficulties:
- Please inform the instructor via E-mail of the problem.
- Please DO NOT SUBMIT any assignments VIA E-MAIL UNDER ANY
CIRCUMSTANCES! Assignments submitted via e-mail will not be accepted. All
assignments must be submitted via Desire2Learn.
Words of Wisdom (TAKE THIS PART SERIOUSLY!)
- In an online class reading for comprehension is critical. When working
through a new task with written instructions, please take the time to read
through all the instructions before beginning. You may even want to take
notes on what you are reading. Don't be the student who after reading the
instructions of "click this link, then click the blue button on the
resulting page" sends an e-mail asking "I clicked the link, what do I do
- Skills Practice is essential for learning success. When learning new
skills that will be assessed on exams, be sure to practice examples in
order to gain the confidence to perform that skill on the exam. Not all
skills practice will be graded work. Nontheless, it is essential to
practice skills for both understanding and mastery. It is essentially that
skills practice items be worked on before the assessments even though the
final assessment on those items occur at the end of the semester with the
- Start assignments early. This way, you can ask questions and clarify
things that are confusing. Be sure to take a look at the homework when you receive it and not an hour before it is to be turned in!
- If you cannot keep up with the pace of this class,
please talk with your professor as soon as possible. Please do not simply
drop the class without first discussing your situation.
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
So it is
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
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.
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 firstname.lastname@example.org. Students can reach the 24/7
Support Line by calling 833-855-0084.
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: https://clayton.libanswers.com
Find your personal librarian: https://clayton.libguides.com/liaison
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
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