Detailed schedule and class resources

Class 1: Tuesday, January 26

Class 2: Friday, January 29

You can ignore the discussion of "order at most", "order at least", and "same order of magnitude" on page 6. In class, we will concentrate on the definition of a graph, and on revising proof by induction (previously covered in the discrete math course). Most of the other material in this section will be required later, but we will revisit such material when needed.

Class 3: Tuesday, February 02

Note the definition of "language" given near the bottom of page 18. The lecture will emphasize two different views of what a "language" can mean to a computer scientist: 1. a programming language, and 2. the answer to a mathematical problem (more specifically, a list of numbers that satisfy some given property, such as being prime or being even).

Mini-lab to understand basics about grammars:

• fire up JFLAP. Click on grammar. Create your own grammar. (Use S as the start symbol. Use uppercase letters as variables, lowercase letters as terminal symbols.)
• Choose "multiple brute force parse". In the frame on the right, in the input column, enter a string you believe is in the language defined by your grammar. Click "run inputs" and check that "accept" is the result.
• Now click "start" in the top-left frame. Click "step" a few times. Switch between inverted tree and derivation table, try to understand what is being shown here.
• Step through the derivation of another string that is in your language; this time ensure the string has length at least 4.
• Find a string that is not in your language; make sure that the result is "reject". Find several more strings that get rejected.
• Find the three shortest strings that are accepted. Find the three shortest strings that are rejected.

Class 4: Friday, February 05

The lecture will briefly mention some of the material in Linz 1.3, but this section is not required reading.

This class will include a mini-lab using JFLAP to investigate some rudimentary dfas.

Class 5: Tuesday, February 09

JFLAP mini-lab to investigate non-determinism.

Class 6: Friday, February 12

JFLAP mini-labs to practice converting between nfa and dfa. JFLAP files for Linz examples are available: fig2.12.jff, fig2.14.jff.

Class 7: Tuesday, February 16

grep minilab

Class 8: Friday, February 19

If time permits, continue with the same grep minilab as last time.

Class 9: Tuesday, February 23

A summary of converting between different descriptions of regular languages is provided.

Minilab suggestion: JFLAP provides interactive demos of almost every conversion in the summary mentioned above. We have covered some of them in previous minilabs. Explore as many of the other conversions as possible, both in the lecture today and in your own time.

Class 10: Friday, February 26

Minilab: Start working on question 0.2 of programming assignment 2. Run the example code as given, and experiment with metacharacters such as \s, \w, \S, \W, \b. Now change the code so that the regular expression is hardwired as a literal string in the code itself. Again experiment with a range of metacharacters.

Class 11: Tuesday, March 02

No minilab. Instead, we work on examples demonstrating more interesting closure properties.

Class 12: Friday, March 05

Here is a proof of Linz example 4.6 (p114) that resembles the pumping lemma more closely than the proof given in the book. It is strongly recommended you master this proof (you should be able to write out the second, abbreviated version).

Class 13: Tuesday, March 09

Check out the cool math in today's pumping lemma handout.

Class 14: Friday, March 12

Class 15: Tuesday, March 23

minilab: Try out a few of the pumping lemma examples on JFLAP.

Class 16: Friday, March 26

Note that there will be some changes based on the midsemester feedback.

minilab: Explore brute force parsing in JFLAP: 1. run JFLAP's brute force parser on the grammar S->aA|AbS,A->a|SA, with w=abaa -- ensure you understand the result. 2. create a grammar, and a string that you are sure is in the grammar, such that JFLAP needs more than 20 seconds to find it using brute force parse. 3. same as (2), but your grammar may have only two rules. 4. same as (3), but make the string as short as possible. 5. plot time as function of string length. Explain.

Class 17: Tuesday, March 30

minilab: practice each type of grammar transformation in JFLAP. Here are some simple grammars on which to try each type of transformation: useless1.jff, useless2.jff, lambda.jff, unit.jff, chomsky.jff, combine everything.

Class 18: Friday, April 02

minilab: Implement an npda for a^n b^n in JFLAP.

Class 19: Tuesday, April 06

minilab: 1. (skipped from last time) Implement an npda for a^n b^n in JFLAP. 2. implement an npda for the language generated by the grammar S->aSbbb|aab (Hint: Try to write out a description of the language in set notation first.) 3. work on the skipped minilab from class 16.

Class 20: Friday, April 09

Class 21: Tuesday, April 13

Class 22: Friday, April 16

Class 23: Tuesday, April 20

Minilab:

• Download the Universal Turing machine of Lucas and Jarvis (see also their explanatory webpage if you're interested).
• Encode your binary incrementor machine as an input for the Lucas and Jarvis Universal Turing machine. An explanation of the encoding is provided. Lucas and Jarvis provide another explanation on their website.
• Test your encoding: for each of the binary numbers from 0 to 8, increment the number using the Universal Turing machine and an appropriate input string.

Class 24: Friday, April 23

Class 25: Tuesday, April 27

Minilab:

1. Create an unrestricted grammar in JFLAP. Do a brute force parse of at least one string that is in the language and requires use of one of your unrestricted productions.
2. Design an unrestricted grammar for a^n b^n c^n and test it in JFLAP using brute force parsing. Be prepared to explain your design to the rest of the class. Move on to the next question if no progress after 10 minutes or so.
3. Download two possible solutions for a^n b^n c^n (solution 1, solution 2). Explore them in JFLAP. For at least one of the solutions, be prepared to explain how it works to the rest of the class. What is the main practical difference between these two solutions?

Class 26: Friday, April 30

Class 27: Tuesday, May 04

Class 28: Friday, May 07

Chris Bishop's 2008 Royal Institution Christmas Lectures. We watched segment 3 of lecture 3.