CptS 317: Automata and Formal Languages
Syllabus, Fall 2024
Last updated: August 25, 2024

Course Information
Credit Hours: 3Semester: Fall 2024
Meeting Times: MWF, 3:10–4:00 pm
Meeting Location: SPRK G0010
Learning Management System: Canvas will be used for the management of this course, including for posting of lecture materials, assignments, announcements, and messages. It will also be
used for handling student submissions and instructor and Teaching Assistant feedbacks.

Instructor Information
Instructor: Assefaw Gebremedhin
Office: EME B43
Email: assefaw.gebremedhin@wsu.edu
Webpage: https://eecs.wsu.edu/~assefaw/
Instructor Office Hour: Fridays 12:00–1:30pm
Office hour will be conducted in-person, but I will also make a zoom option available in case you
can’t make it in person. Zoom meeting information is posted on the Canvas site of the course.
Teaching Assistant 1: Bryan Frederickson
Email: bryan.frederickson@wsu.edu
Office Hour: Mondays 4:30–6pm
Teaching Assistant 2: Martin Hundrup
Email: martin.hundrup@wsu.edu
Office Hour: Wednesdays 4:30–6pm
Teaching Assistant 3: Haridhar (Harry) PulivarthyEmail: haridhar.pullivarthy@wsu.edu
Office Hour: Fridays 5:30–7pm
Teaching Assistant 4: Angel Ramirez
Email: angel.ramirez1@wsu.edu
Office Hour: Tuesdays 10:30am–12pm
Teaching Assistant 5: Roy Zabetski
Email: roy.zabetski@wsu.edu
Office Hour: Thursdays 10:30am–12pm
TA Office Hours Location: Each TA Office Hour will take place in person in DANA 115. I will
also make a zoom option available in case you can’t make it in person. Zoom meeting informationis posted on the Canvas site of the course.

1

Course Objectives• Introduce concepts in automata theory and theory of computation• Identify different formal language classes and their relationships• Design grammars and recognizers for different formal languages• Prove theorems in automata theory and language properties• Determine the decidability and intractability of computational problems

Prerequisites• CptS 122/132 Data Structures• Math 216 Discrete Structures

Text book• Introduction to the Theory of Computation, Third Edition by Michael Sipser. 2013.

Learning Outcomes
At the conclusion of this course students will:• Have acquired a fundamental understanding of the core concepts in automata theory andformal languages• Be able to design grammars and automata (recognizers) for different language classes• Be able to identify formal language classes and prove language membership properties• Be able to prove theorems establishing key properties of formal languages and automata• Have acquired a fundamental understanding of core concepts relating to the theory of computation and computational models including decidability and intractability

Coursework and Assessment
Coursework:• 7 homework assignments (58%)• 2 midterm exams (20%)• 1 final exam (20%)• Class Participation (2%)– Active class participation—in discussions during lectures, surveys, and other online discussions, including responding to Participation Question of The Day—is required. ClassParticipation will count towards 2% of the final grade.
Homework policy:• Submissions happen electronically via Canvas.
• Submissions are required to be in PDF format. You can hand-write your solution to anassignment or type it up using a computer. If you hand-write, make sure your writing islegible and clean.
• All homework assignments must be done individually.
• Missing or Late Work: Students are expected to submit assignments by the specified due
date and time. Assignments turned in up to 48 hours late will be accepted with a 10% grade
penalty per 24 hours late. Except by prior arrangement, missing or work late by more than
48 hours will be counted as a zero.
2

Exam policy:• The dates for the two midterm exams are tentatively set for September 25 and October 28.
If changes are made to these tentative dates, the exact dates will be announced in class andalso updated in the syllabus at least two weeks before the exam date.
• The final exam is on December 9.
• All three exams are closed-book, closed-notes, written exams.
• The final exam is comprehensive.
• Missed Exam: Make-up exam is not allowed if any exam is missed unless there is an
extra-ordinary circumstance. A missed exam will be counted as a zero.

Grading
Final letter grades will be given according to the following ranges:
A (93–100%), A- (90–92.99%), B+ (87–89.99%), B (83–86.99%), B- (80–82.99%), C+ (77–79.99%),
C (70–76.99%), C- (67–69.99%), D (60–66.99%), F (less than 60%).

Expectations for Student Effort
For each hour of lecture equivalent, students should expect to have a minimum of two hours ofwork outside class.

Course Topics
Here is an outline of major topics (modules) of the course.
1. Introduction
2. Regular Languages
3. Context-free Languages
4. Church-Turing Thesis
5. Decidability
6. Reducibility
7. Time Complexity

Weekly Schedule
See Table 1 for a weekly schedule of topics and assignments.

Policies
Conduct
Students are expected to maintain a professional and respectful classroom environment. In particular, this includes:• silencing personal electronics (non-disruptive devices may be used during class)• arriving on time and remaining throughout the class.

3

WeekTopics

01 (Aug 19–23)
02 (Aug 26–30)
03 (Sep 2–6)
04 (Sep 9–13)
05 (Sep 16–20)
06 (Sep 23–27)
07 (Sep 30–Oct 4)
08 (Oct 7–Oct 11)
09 (Oct 14–18)
10 (Oct 21–25)
11 (Oct 28–Nov 1)
12 (Nov 4–8)
13 (Nov 11–15)
14 (Nov 18–22)
15 (Nov 25–29)
16 (Dec 2–6)
17 (Dec 9–13)

Assignments/comments

Intro to course, intro to computation theory
Review of math concepts, prooftechniques, finite automata
Finite Automata
Regular Expressions
Nonreguar Languages
Context-free Languages
Context-free Grammars
Pushdown Automata
CFG and PDA equivalence
Minimization of Automata; Deterministic CFL
Turing Machines I
Turing Machines II
Decidability
Reducibility
Thanksgiving breakTime Complexity, Review
Finals Week

HW0 (survey) out
HW0 in; HW1 out
No class 9/2; HW1 in, HW2 out
HW2 in, HW3 out
HW3 inMid-term 1 on 9/25
HW4 out
HW4 in, HW5 out
HW5 in
Review for Mid-term 2Mid-term 2 (10/28); HW 6 Out
HW6 inNo class 11/11; HW 7 out
HW 7 inPracticeFinal Exam on Dec 9

Table 1: Tentative week-by-week schedule of topics and assignments.

Use of Generative AI Tools and Technologies
The use of generative AI tools and technologies, such as GPT, is allowed for learning purposes
about material related to this course. However, using generative AI tools to produce solutions forgraded assignments is not permitted. Any solution you submit for grading for homeworks must be
your own work.
Correspondence
All class related correspondence with the instructor will be made via Canvas.
Attendance
Regular attendance is expected. While students may miss class for urgent reasons, repeated absences that are not cleared with the instructor will factor into the Class Participation portion ofthe grade.

4

Academic Integrity
Academic integrity is the cornerstone of higher education. You are responsible for reading WSU’s
Academic Integrity Policy, which is based on Washington State law.
If you cheat in your work in this class you will:• Fail the assignment or exam in which the cheating happened.
• Be reported to the Center for Community Standards.
• Have the right to appeal my decision.
• Not be able to drop the course or withdraw from the course until the appeals process isfinished.
If you have any questions about what you can and cannot do in this course, ask me.
If you want to ask for a change in my decision about academic integrity, use the form at theCenter for Community Standards website. You must submit this request within 21 calendar daysof the decision.

Lauren’s Promise:
WSU’s Commitment to Address Discrimination and Harassment
On October 22, 2018, Lauren McCluskey, 21 years old, was murdered by a man she briefly dated
on the University of Utah campus, where she was a student. Lauren was raised in Pullman,Washington. Together with her parents, who are professors at WSU, this university community
stands firmly behind Lauren’s Promise: WSU will listen and facilitate support and reporting
options if someone is threatening you.
WSU prohibits discrimination and harassment. This includes discriminatory harassment, hatecrimes, sexual discrimination, sex-based harassment, stalking, dating violence, domestic violence,
sexual assault, and all types of sexual violence.
If you are in immediate danger, call 911.
If you have experienced or have witnessed discriminatory behavior, you can contact the WSU
Compliance and Civil Rights (CCR) and/or the WSU Title IX Coordinator. CCR can provide
information on reporting options, including confidential resources available to you, and facilitate
supportive measures. To contact CCR:
Online: Online Reporting Form
Email: ccr@wsu.edu
Phone: 509-335-8288
For more information, see the WSU Policy Prohibiting Discrimination and Harassment (Executive Policy 15), WSU Standards of Conduct for Students (Chapter 504-26 WAC), and the WSU
Notice of Nondiscrimination.
Reasonable Accomodation
Students with disabilities or chronic medical or psychological conditions can request reasonableaccommodations. If you need reasonable accommodations to fully participate in your courses,
please go to your campus’ Access Center/Services website (see links below). Follow the procedures
to request accommodations. You may also contact your campus office to schedule an appointment
with an Access Advisor.

5

The Access Center/Services will notify your instructors of your requested accommodations, but
you may need to communicate with your instructors about how some of your accommodations will
work (by email, Zoom, or in person).
Contact an Access Advisor on your campus:• Pullman, WSU Global Campus, Everett, Bremerton, and Puyallup:509-335-3417, http://accesscenter.wsu.edu, or email access.center@wsu.edu• Spokane: 509-358-7816, https://spokane.wsu.edu/studentaffairs/access-resources/,or email spokane.access@wsu.edu• Tri-Cities: 509-372-7352, http://www.tricity.wsu.edu/disability/,or email tricities.AccessServices@wsu.edu• Vancouver: 360-546-9238,
https://studentaffairs.vancouver.wsu.edu/access-center,or email van.access.center@wsu.edu
Emergencies on Campus
To receive emergency alerts on your phone or by email, click on the link to the page of your campusthat you can access via this university syllabus website:
https://syllabus.wsu.edu/university-syllabus/.
These alerts may include information about active shooter situations and severe weather.
In case of an active shooter, follow these ideas: “Run, Hide, Fight”.
In any emergency, remain ALERT by observing and paying attention to WSU emergency alerts.
ASSESS your specific situation, and ACT to ensure your own safety and the safety of others if you
are able.

Other Policies in the University Syllabus
Students are responsible for reading and understanding all university-wide policies and resources
pertaining to all courses (for instance: accommodations, care resources, policies on discriminationor harassment), which can be found in the university syllabus website:
https://syllabus.wsu.edu/university-syllabus/.

Academic Dates and Deadlines
Students are encouraged to refer to the academic calendar often to be aware of critical deadlines
throughout the semester. The academic calendar can be found at
http://registrar.wsu.edu/academic-calendar.

ChangesThis syllabus is subject to change. Updates will be posted on the course website.

6