CS 462/662 - Formal Languages and Parsing

Winter 2020

Mon-Wed, 10:00 AM to 11:20 AM, DWE 1502. First class is Monday, January 6, 2020.

Mondays will be devoted to lectures. Wednesdays will be devoted half to lecture, and half to a problem-solving session in small groups after the first week.

Summaries of all lectures are here.

Office: DC 3134

Phone: x34804

Office Hours: Wednesdays, 2:30 PM - 3:30 PM, in DC 3134, 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 busy, so please don't knock.

Office hours: Thursdays, 11:30 AM - 12:30 PM,

- in DC 2102 on January 9 and January 16
- in DC 2136B starting January 23 2020.

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 11 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 at 5 PM sharp as follows:

Assignment Number Handed Out Due ---------------------------------------------------------------------- 1 Friday January 10 Friday January 17 2 Friday January 17 Friday January 24 3 Friday January 24 Friday January 31 4 Friday January 31 Friday February 7 5 Friday February 7 Friday February 14 6 Friday February 14 Friday February 28 7 Friday February 28 Friday March 6 8 Friday March 6 Friday March 13 9 Friday March 13 Friday March 20 10 Friday March 20 Friday March 27 11 Friday March 27 Friday April 3Turn in your assignments, in

1. Go to the course page on LEARN.

2. From the "Assessments" dropdown menu near the top of the page select "dropbox." You will be redirected to a new page.

3. Select the appropriate assignment on the new page to submit to its dropbox.

You should prepare your solutions using a document preparation system such as LaTeX or (ugh!) Microsoft word. Do *not* write text by hand and scan. However, for figures only (like automata), feel free to sketch by hand and scan in the results. (If you're ambitious and want to learn some new software, one easy thing to learn is gv/dot for drawing automata.) One file per assignment, please.

Late policy: no late assignments. Any assignments received after
5 PM on Fridays **will
receive no credit**. Your single lowest mark out of all 11
assignments will be discarded.

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. Assignment mark challenges must be
initiated within **one week** of the time the assignment mark
was posted.

There will be no midterm.

There will be a take-home final exam which is worth 40% of the mark. It will consist of some easy problems and some challenging ones.

The remaining 10% of the mark will come from the group problem-solving sessions, held on Wednesdays. Each student is expected to present the the solution to at least one problem during the term.

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%

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, Facebook,
chat groups, newsgroups, etc.
and requesting hints or solutions is not permitted.**

The level of detail in a solution we expect is *enough to convince
a skeptical TA*. You can always use anything from a
previous course, or the textbook, just by citing it.

*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.

We'll be using Piazza to distribute information and allow discussion,
and to issue corrections and clarifications to homework assignments and the take-home final. Please do *not* post public requests for hints,
or questions that give away too much about the solution to problems.

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.

- Jeffrey Shallit,
*A Second Course in Formal Languages and Automata Theory*, Cambridge University Press, 2009. The book will be 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.