CS 462/662 - Formal Languages and Parsing

Winter 2015

Tu-Th, 1:00 PM - 2:20 PM, CPH 3604.

Two ways to get there:

Outdoors (1) Enter CPH building from loading dock along ring road, walk to 3rd floor;

Indoors (2) Walk SSE from Davis Centre 2nd floor to E3, descend
to 1st floor, continue walking until you hit T-junction,
take staircase up one floor, exit to the right and walk
ENE to classroom.

Tuesdays will be devoted to lectures. Thursdays will be devoted half to lecture, and half to a problem-solving session in small groups.

Jeffrey Shallit

Office: DC 3134

Phone: x34804

Office Hours: Mondays, 10:00 AM - 11:00 AM,
or by appointment, or just stop by when my office
door is open. If my office door is closed, I'm either not in or taking
a nap, so please don't knock.

Also, there will be "virtual office hours" held every week from 9 PM to 10 PM on the Monday right before the assignments are due, via AOL Instant Messenger. My userid there is "CS462Prof". Join me there, anonymously or not, to ask any questions you want.

Chen Fei Du

Office: DC 2569 Desk #9

Office Hours: Fridays, 2 - 3 PM

CS 360 or CS 365 or equivalent.

Models of computation such as the Turing machine and the random access machine (RAM) are so powerful that it is quite difficult to prove explicit theorems about what they can and cannot compute.

In the late fifties and early sixties,
mathematicians and computer scientists
began to study simpler models of computation such as the
*finite automaton* and the *pushdown automaton*. These
models of computation were later found to have many practical
applications: regular expressions (used in editing and filename
specification); parsing and compiling computer languages; specification
(LEX and YACC), etc.

Building on CS 360/365, this course discusses more advanced topics in formal languages and automata theory. Topics that we will discuss include: Thue's problem, the Lyndon theorems, combinatorics on words, closure properties of regular sets, the Myhill-Nerode theorem, ambiguity of CFG's, inherent ambiguity, the Chomsky hierarchy, DCFL's, and other language classes.

We will also cover some "real-life" applications including:
phases of compilation, top-down parsing, LL(1) grammars, bottom-up
parsing, LR(0) grammars, and LR(*k*) grammars.

There will be 10 problem sets, with problems of varying difficulty. These will be worth 50% of the mark. You should expect to spend 4-5 hours a week on these problems.

The assignments will be handed out and due as follows:

Assignment Number Handed Out Due ---------------------------------------------------------------------- 1 Tuesday, January 13 Tuesday, January 20 2 Tuesday, January 20 Tuesday, January 27 3 Tuesday, January 27 Tuesday, February 3 4 Tuesday, February 3 Tuesday, February 10 5 Tuesday, February 10 Tuesday, February 24 6 Tuesday, February 24 Tuesday, March 3 7 Tuesday, March 3 Tuesday, March 10 8 Tuesday, March 10 Tuesday, March 17 9 Tuesday, March 17 Tuesday, March 24 10 Tuesday, March 24 Thursday, April 2Hand your assignments in during class. Late policy: solutions to problem sets will be handed out in the class on the due date; any assignments received after that time

If you have questions about how your assignment was marked, please contact the TA first. If you are still not satisfied, then you can contact the instructor.

There will be no midterm.

There will be a take-home final which is worth 40% of the mark. It will consist of some easy problems and some challenging ones. Collaboration of any kind is not allowed on the final.

The remaining 10% of the mark will come from the group problem-solving sessions, held on Thursdays. Each student is expected to present the the solution to at least one problem during the term. Your mark will depend on the quality and quantity of problems you present, the clarity of your writeup, and the difficulty of the problems.

Graduate students will be expected to complete a term project in addition to the other work. For graduate students, the mark breakdown will be: problem sets, 40%; final project, 15%; problem-solving session, 10%, and final exam, 35%. The project involves reading papers from the literature about a topic in formal languages or parsing of your choice, and then writing a short (5-15 pages) report on what you have learned.

There is a list of Open Problems related to the course material. Solve any of them and get an automatic 100 for the course!

For the homework problem sets,
you are permitted to discuss *general aspects* of them
with other students in the class, but each person should hand in
his/her own copy of the solutions.
Plagiarism - using outside sources without
documentation - will be dealt with severely.
**Posting problems on Internet bulletin boards, chat groups, newsgroups, etc.
and requesting hints or solutions is not permitted.**

*Any* use of outside sources
(people, books, articles, etc.) *must*
be documented in anything you hand in for this course. You are
welcome to use outside sources, but remember
that the goal is to *learn*: you should try to solve the
problems on your own first. When in doubt about whether you need
to cite something, err on the side of caution.

The Mathematics Faculty standard penalty for cheating on assignments is a grade of -100% for the assignment, with a minimum deduction of 5% from the final course mark. See the document Cheating and the Student Academic Discipline Policy for more details.

We'll be using Piazza to distribute information and allow discussion. (There is a
newsgroup for the course -- ` uw.cs.cs462`, but we won't be using it.)
I will use Piazza to issue corrections and clarifications
to homework assignments and the take-home final.

Course marks will be available on LEARN.

The course web page has copies of problem sets, hints for getting better marks, errata for the course textbook, cheating policy, and summaries for every lecture.

E-mail to my account gets read promptly, and usually answered promptly.

- Jeffrey Shallit,
*A Second Course in Formal Languages and Automata Theory*, Cambridge University Press, 2009. The book is available at the University bookstore, and there's a copy on reserve here: QA267.3.S53 2009 at the Davis Centre Library.

There's a little more about the book, including errata, here.