CptS 317: Automata and Formal Languages — Spring 2020 — Syllabus

Course Information

Credit Hours: 3
Semester: Spring 2020
Meeting times and location: MWF, 10:10-11:00, SPRK G0010
Course website: CptS 317: Automata and Formal Languages | | Washington State University (wsu.edu)
The course website will be used to post this syllabus and related resources. Additionally, the online portal OSBLE+ (plus.osble.org) will be used for posting lecture material, assignments, announcements, and messages.

Instructor Information

Instructor: Assefaw Gebremedhin
Offce: EME B43
Email: assefaw DOT gebremedhin AT wsu DOT edu
Homepage: www.eecs.wsu.edu/~assefaw

Office hours: Wednesdays 1:30-2:30pm, or by appointment.

Teaching Assistant: Papa James Halvorsen
Email: james DOT Halvorsen AT wsu DOT edu
Office Hours: Mondays 2–3pm and Thursdays 4–5pm
Office: Dana 115 (Data Science Lab)

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 or disprove theorems in automata theory using its properties
Determine the decidability and intractability of computational problems

Prerequisites

CptS 122/132
Math 216

Textbook

Main textbook:

Introduction to the Theory of Computation, Third Edition, Michael Sipser.

The following book is a good additional reference:

Introduction to Automata Theory, Languages, and Computation, Third Edition by John Hopcroft, Rajeev Motwani and Jeffrey D. Ullman.

Grading and Course Policies

8 homeworks (60%) — best 7 out of 8 will be used toward final grade
2 midterms (20%)
1 final exam (20%)

Homework policy:

Homeworks must be submitted in class as hard copy on the due date mentioned in the home-
work. Early submissions are allowed.

All homeworks must be done individually.
No late submissions (without permission) are allowed.

Exam policy:

Closed book, closed-notes, comprehensive
Midterm exam dates will be announced in class and also updated in the syllabus as the exams approach.

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%).

Learning Outcomes

At the conclusion of this course students will:

Have acquired a fundamental understanding of the core concepts in automata theory and
formal 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 and disprove 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

Topics

Here is a tentative outline of topics. Most of them map to roughly a week.

Introduction to automata theory
Finite Automata (DFA and NFA)
Regular expressions and languagues
Properties of regular languages: pumping lemma, closure properties, decision properties, equivalence and minimization of automata
Context-free grammars and languages
Pushdown Automata
Properties of context-free languages
Turing machines and extensions
Undecidability, diagonalization, problem reduction
Intractable problems: P and NP, NP-completeness

Policies

Correspondence:

All class related correspondence with the instructor will be made via OSBLE+. I will check messages sent to my inbox on a regular basis, and will do my best to respond promptly. Students are encouraged to choose their OSBLE+ settings so that they get emails notifications when messages are sent or posted.

Academic Integrity:

Academic integrity is the cornerstone of higher education. As such, all members of the university community share responsibility for maintaining and promoting the principles of integrity in all activities, including academic integrity and honest scholarship. Academic integrity will be strongly enforced in this course. Any student who violates the University’s standard of conduct relating to academic integrity will receive an F as a final grade in this course, will not have the option to withdraw from the course and will be reported to the Office of Student Standards and Accountability. Cheating is defined in the Standards for Student Conduct WAC 504-26-010 (3). You can learn more about Academic Integrity on the WSU campus at conduct.wsu.edu. Please also read this link carefully: EECS Academic Integrity Policy. Use these resources to ensure that you do not inadvertently violate WSU’s standard of conduct.

Safety on Campus:

Washington State University is committed to enhancing the safety of the students, faculty, staff,
and visitors. It is highly recommended that you review the Campus Safety Plan (safetyplan.wsu.edu/) and visit the Office of Emergency Management web site (oem.wsu.edu/) for a comprehensive listing of university policies, procedures, statistics, and information related to campus safety, emergency management, and the health and welfare of the campus community.

WSU Classroom Safety:

Classroom and campus safety are of paramount importance at Washington State University, and are the shared responsibility of the entire campus population. WSU urges students to follow the “Alert, Assess, Act” protocol for all types of emergencies and “Run, Hide, Fight” response for an active shooter incident. Remain ALERT (through direct observation or emergency notification), ASSESS your specific situation, and act in most appropriate way to assure your own safety (and the safety of others if you are able).

Please sign up for emergency alerts on your account at MyWSU. For more information on this subject, campus safety and related topics, please view the FBI’s Run, Hide, Fight video and visit the WSU safety portal (Classroom Safety).

Students with Disabilities:

Reasonable accommodations are available for students with a documented disability. If you have a disability and need accommodations to fully participate in this class, please either visit or call the Access Center (Washington Building 217; 509-335-3417) to schedule an appointment with an Access Advisor. All accommodations must be approved through the Access Center. For more information, consult the webpage accesscenter.wsu.edu or email at Access.Center@wsu.edu.

Important 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. Weather Policy
For emergency weather closure policy, consult: alert.wsu.edu.

Weather Policy:

For emergency weather closure policy, consult: alert.wsu.edu.

Changes:

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