1
CPT S 317: Automata and Formal Languages
Spring 2017School of EECSWashington State University, PullmanMWF 10:10-11:00SLOAN 169
2
Instructor Contacts
Instructor:AnanthKalyanaraman(pronounced: “An-anth” “Kal-ya-na-ra-man”)EME [email protected] Hours:Wednesdays 2:30-3:30pm
3
Objectives
Introduce concepts in automata theory and theory of computationIdentify different formal language classes and their relationshipsDesign grammars and recognizers for different formal languagesProve or disprove theorems in automata theory using its propertiesDetermine the decidability and intractability of computational problems
4
Course Organization
Very broadly, the course will contain three parts:Part I) Regular languagesPart II) Context-free languagesPart III) Turing machines & decidability
5
Teaching Assistants
TA1TBDTA2:TBDCheck course website for any updates
6
Pre-requisites
CPT S 122/132: Data StructuresMath 216: Discrete Structures
7
Required Textbook
Introduction to Automata Theory, Languages and ComputationBy J.E. Hopcroft, R. Motwani, J.D. Ullman3rdEditionAddison Wesley/PearsonCourse book homepage:http://infolab.stanford.edu/~ullman/ialc.htmlSolutions to starred exercises in the textbook & ErrataOSBLE+ (Online Studio-Based Learning Environment):http://plus.osble.orgThe Gradiance Resource (optional)
8
Course Webpage
http://www.eecs.wsu.edu/~ananth/CptS317Why do I need to check the webpage?Lecture NotesHomeworks will be posted on the webpageA tentative schedule will also be posted and maintainedMisc. static information about the courseHow frequently do I need to keep checking the course webpage?Ideally once every day, and if not at least once before/after each class (for lecture notes)
9
The OSBLE+ Web Portal
We will use OSBLE+ for discussions, class announcements, and for email communication with instructor.Every student needs to register in OSBLE+ and should check the portal regularly. All important (dynamic) announcements will be made through this portal.Registration instructions are on the course website.
10
How to get in touch with the instructor and the TA(s)?
OSBLE+ (for email and dashboard public discussion forums)Office hoursWeekly oncepreferred way to meet one-on-oneNo need for prior appointment if meeting during the office hourIn addition, the instructor will be available outside of office hours to meet (appointments preferred for this mode).
11
Grading
8 homeworks (60%) - (best 7 policy)2 midterms (20%)1 final (20%)Grading Policy:Curved
12
Homework Submission Policy
Hardcopy to be submittedin classon the due dateEarly submissions allowedNo late submissionsExtensionsmaybe permitted under extraordinary circumstancesContact the instructorat least 1 week priorHomeworks will be posted on the course website
13
Homework Policy
All homework must be doneindividuallyCheating:Helping others, getting help, looking up website for solutions, etc.Students caught cheating will be awarded anFgrade, and will be subjected to the WSU academic dishonesty policy.If something is not clear, on what constitutes and what does not, please consult the instructor in advance.
14
Exam Policy
2 Midterms and 1 Final exam.Closed book, closed notes, comprehensiveMake-ups will be rare and only under extraordinary circumstancesSeek prior permission from instructor (at least 2 weeks in advance)
15
Course Schedule
A tentative schedule has been posted and will be maintained on the course websiteSubject to change as course progressesBookmark & keep checkingRecommended frequency: once a weekLook for exam schedules as well here
16
Lecture basics
Classes will involveboth Slides + Board(to roughly equal degrees)Lecture slides available onlineHowever, no scribes from class will be made availableSo, take your own notes in classFor latest/updated slides, download before eachuseUse of laptops and smart phonesnotallowed in classroom.
0
Embed
Upload