CPT S 317: AUTOMATA AND FORMAL LANGUAGES

Spring 2017, 3cr.

 

(JAN 9 - May 5)

SCHOOL OF EECS

WASHINGTON STATE UNIVERSITY

 

 

MWF 10:10 - 11:00

SLOAN 169

 

Current announcements    Instructor & TAs contact    Course details    Grading and other course policies    Course online resources

 

Lecture notes    Homeworks    Course schedule   Learning Outcomes

 

 

ACTIVE ANNOUNCEMENTS


  • Homework 8 posted below (due on Wednesday, Apr. 26)
  • Midterm test II on Monday (Apr. 17)
  • Homework 7 posted below (due on Wednesday, Apr. 12)
  • Homework 6 posted below (due on Wednesday, Apr. 5)
  • Homework 5 posted below (due on Wednesday, Mar. 29)
  • Homework 4 posted below (due on Monday, Mar. 20)
  • Homework 3 posted below (due on Friday, Feb. 17)
  • old announcements archive

 

INSTRUCTOR & TAs

 

Ananth Kalyanaraman

Weekly office hours: Wednesdays 3:30-4:30pm @ EME 237
            Email: Through OSBLE+ (http://plus.osble.org)

 

Teaching assistants:

            Mohammad Omar Faruk
            Weekly office hours: Thursdays 11:30am-12:30pm @ Sloan 335
            Email: Through OSBLE+ (http://plus.osble.org)
 

COURSE DETAILS

 

  • 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 

  • Required textbook:

    • "Introduction to automata theory, languages and computation"

    # Authors: JE Hopcroft, R Motwani and JD Ullman

    # Publisher:Addison Wesley/Pearson; 3rd Edition

 

GRADING & 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 hardcopy on the due date mentioned in the homework.  Early submissions are allowed.

  • All homeworks must be done individually. 

  • Late submission policy:
  •     No late submissions will be allowed on any homework. However, earlier submissions are allowed at any time before due date (either in class or can be turned in at the instructor's office).
  •     Extensions may be allowed but only under extraordinary circumstances upon contacting the instructor well in advance (generally at least 1 week prior to the submission date).

Exam policy:    

  • Closed-book, closed-notes, comprehensive
  • Midterm Exam dates and syllabus will be announced in class as the exams approach. Tentative dates for these exams are posted on the course website schedule link. Please make sure you mark these on your calendar. Make-up exams can be offered but are extremely rare and only under excruciating/emergency circumstances. If you have a problem with the date, come and see the instructor well ahead of time (at least 2 weeks prior to the exam).

 

Academic Integrity Policy:
*Please read carefully*

  • What constitutes cheating? Any deviation from the stated homework and exam policies (above) will be considered "cheating" and will be subject to academic dishonesty code. Note that this includes sharing or even showing your solutions with others in the class. Also, looking up solutions on the web should be strictly avoided and if evidence is found, it will be considered cheating.
  • Consequence of cheating: A student who has been conclusively caught cheating in the class will be given an F grade and will also be reported to the WSU academic integrity/student conduct office.  In other words, there will be Zero Tolerance toward cheating.

Academic integrity is the cornerstone of the university. You assume full responsibility for the content and integrity of the academic work you submit. You are allowed to collaborate with classmates only if an assignment allows it explicitly. For collaborative assignments, however, the guiding principle of academic integrity shall be that your submitted work, examinations, reports, and projects must be your own work. Any student who violates the University's standard of conduct relating to academic integrity will be referred to the Office of Student Conduct and may fail the assignment or the course. You can learn more about Academic Integrity on your campus at  http://conduct.wsu.edu. Please also read this link carefully: EECS Academic Integrity Policy   Please use these resources to ensure that you donŐt inadvertently violate WSU's standard of conduct.  


COURSE WEBSITE, OSBLE+

The course will use two different web resources for different purposes:

  1. This "course website" (i.e., this page you are reading now) is where lecture notes and homeworks will be posted, and the course schedule will be maintained. See corresponding links.
  2. The OSBLE+ learning portal will be used for email exchanges, email announcements, and listing of useful web links/resources.
    Please see here for instructions on how to set up your OSBLE+ account and other personal settings. This is NOT an optional step. All students enrolled in this class should take care of this by the first week of the semester.

 

LECTURE NOTES

 

 

COURSE SCHEDULE

 

 

HOMEWORKS

    (PDFs to be published here as homeworks are posted)

 

LEARNING OUTCOMES

 

  • Acquire a fundamental understanding of the core concepts in automata theory and formal languages.

  • An ability to design grammars and automata (recognizers) for different language classes.
  • An ability to identify formal language classes and prove language membership properties.
  • An ability to prove and disprove theorems establishing key properties of formal languages and automata.
  • Acquire a fundamental understanding of core concepts relating to the theory of computation and computational models including (but not limited to) decidability and intractability.


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 (http://safetyplan.wsu.edu/) and visit the Office of Emergency Management web site (http://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

 

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.

 

ANNOUNCEMENTS ARCHIVE


  • Homework2 has been posted below.
  • Homework 1 has been posted below (see under Homeworks section).
  • Location for TA office hours updated below.
  • Please see updated office hours schedule for the instructor and the TA.
  • Welcome to the class of Spring 2017! Please bookmark this website for your course. You will also need an OSBLE+ account (http://plus.osble.org) which is an online portal that will be used for all class related announcements and emails. Instructions are here.