CPT S 317: AUTOMATA AND FORMAL LANGUAGES

Spring 2009, 3cr.

 

(JAN 12 - May 8)

SCHOOL OF EECS

WASHINGTON STATE UNIVERSITY

 

 

MWF 13:10 - 14:00

SLOAN 233

 

COURSE DETAILS

 

The primary objectives of this course is as follows:

• 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

 

INSTRUCTOR

 

ANANTH KALYANARAMAN

EME 237, 335-6760

Office hours:  MON  4-5pm

 

EMAIL and eLearning:

    Emails to the instructor or the TAs should be sent through eLearning .

    eLearning course website:    http://elearning.wsu.edu

    Alternate email:  ananth@eecs.wsu.edu (use only if eLearning site is down)

 

TEACHING ASSISTANTS

 

            Haiqin Liu

            EME 205  

            Office hours: THU 3-4pm

 

 

ANNOUNCEMENTS (recent)

 

• (4/29) FINAL EXAM is on Monday, 3:10-5:10pm in class
• (4/29) Undecidability lecture slides are also available now on the Lecture Notes link
• (4/20) COURSE EVALUATIONS:      http://skylight.wsu.edu/s/0bf287ce-6f5a-45ce-b6eb-261235507678.srv
• old announcements archive

 

 

PREREQUISITES

 

• CPTS 122
• MATH 216 or equivalent

 

TEXTBOOKS (REQUIRED)

 

• Introduction to automata theory, languages and computation

# Authors: JE Hopcroft, R Motwani and JD Ullman

# Publisher:Addison Wesley/Pearson; 3^rd Edition

 

 

GRADING

• 8 homeworks (60%)

•  2 midterms (20%)

• 1 final exam (20%)

 

 

LECTURE NOTES

 

 

COURSE SCHEDULE

 

 

HOMEWORKS

 

• Homework 1  (due 1/28)
• Homework 2 (due 2/4)
• Homework 3 (due 2/18)
• Homework 4 (due 3/6)
• Homework 5 (due 3/25)
• Homework 6 (due 4/1)
• Homework 7 (due 4/15)

• Homework 8 (due 4/24)

 

COURSE POLICIES

Homework policy:

• Homeworks must be submitted in class on the due date.

• All assignments must be done individually. Anyone cheating will receive a zero for that assignment and will be subject to the university's academic dishonesty/integrity policy. Cheating involves giving assistance to or receiving assistance from another individual.

   

  Academic Integrity Policy (please read)

 

Late submission policy:

• No late submissions will be allowed on any assignment
• Extensions may be allowed under extraordinary circumstances upon contacting the instructor at least 1 week prior to the submission date.

Exam policy:     Closed-book, closed-notes, comprehensive

 

USEFUL LINKS AND WEB RESOURCES

 

Check the eLearning portal: http://elearning.wsu.edu

 

                         If there is a need for special accommodation based on disability, click here.

 

 

SAFETY ON CAMPUS

 

http://www.ba.wsu.edu/em/emergencies.htm

 

Get familiar with the emergency procedures from the above link.

 

STUDENTS WITH DISABILITIES

 

Reasonable accommodations are available for students with a documented disability. If you have a disability and may need accommodations to fully participate in this class, please visit the Disability Resource Center (DRC). All accommodations MUST be approved through the DRC (Admin Annex Bldg, Room 205). Please stop by or call 509-335-3417 to make an appointment with a disability specialist.

 

ANNOUNCEMENTS ARCHIVE