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

We will be using the following five languages as running examples throughout the course:

1. Java programs, written in ASCII
   • an ASCII string is in the language if it can be compiled by the Java compiler with no errors
2. HTML pages, written in ASCII
   • an ASCII string is in the language if it is accepted by the HTML validator at http://validator.w3.org/. (Example of page with an error: deliberate-error.html)
3. multiples of 5, written in decimal
   • a string of decimal digits is in the language if it represents an integer that is a multiple of five
4. prime numbers, written in decimal
   • a string of decimal digits is in the language if it represents an integer that is a prime number
5. Java programs that can't crash (i.e. throw a runtime exception)
   • an ASCII string is in the language if it can be compiled by the Java compiler with no errors, and the resulting program will never throw a runtime exception, no matter what input it receives.

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

Mini-lab using JFLAP to investigate some rudimentary dfas:

• In JFLAP, create a dfa that accepts strings of one or more 'a's, optionally preceded by a single 'b'.
• Test your dfa using "multiple run".
• Does your dfa have transitions for every possible input? If not, it is incomplete, according to the definition given in our textbook, but JFLAP allows this kind of incomplete dfa. What is the interpretation of a missing transition?
• If your dfa is complete, delete a few transitions to make it incomplete. Now use the "add trap state" functionality to complete it.

Class 5: Monday, February 7

A note on nondeterminism: Nondeterminism does not exist in any real computer. It is a theoretical concept that we introduce for convenience, because it is often much easier to prove facts about nondeterministic automata, compared to deterministic automata. There are two useful ways to think about nondeterminism:

1. Imagine a computer with supernatural powers that can examine multiple possibilities at the same time. For example, consider a supernatural chess computer that could simultaneously analyze the consequences of 10 different possible moves. Instead of having to make a deterministic choice about which of the 10 moves to analyze, this computer can make a nondeterministic choice to analyze all 10 moves at once!
2. It is always possible to simulate nondeterminism on a real computer, in the following way. Whenever a (supernatural) computer wants to make a nondeterministic choice, we just make a list of the possible choices available, and store them in a queue in our (real) computer's memory. Then, analyze each of the choices one at time. If further nondeterministic choices are encountered, add them to the queue and analyze them later too.

JFLAP mini-lab to investigate non-determinism:

1. In JFLAP, implement an nfa that accepts the language: {aaa or an even number of a's}
2. Use the "step with closure" option to see how the nfa processes the following two strings: aaaaa, and aaaa. You will repeatedly click on the "step" button to do this. Once you understand the effect of the "step" button, investigate the effect of the other buttons (reset, freeze, thaw, trace, and remove).
3. Now practice using nondeterminism that arises from transitions on the empty string. Implement an nfa for the language {aaaa, aaaba}, using at least one transition on the empty string. Use "step with closure" to investigate the workings of this nfa.
4. Add more nondeterminism to your nfa. Practice stepping through sets of states, freezing and/or removing some of them.

Class 6: Thursday, February 10

We will do two JFLAP mini-labs to practice converting between nfas and dfas, based on examples from Linz. JFLAP files for these Linz examples are available: fig2.12.jff, and fig2.14.jff.

Important hints for using JFLAP to convert from an nfa to a dfa:

• Typically, you will only use the second tool, labeled "expand group on terminal". To use this tool, always click on an existing state that needs a new transition, drag away from that state, and release.
• The other tools can be used to skip some steps and complete the conversion more quickly, but they won't help you to learn the algorithm.
• JFLAP doesn't let you insert trap states during the conversion from nfa to dfa, so you can ignore transitions that end in the empty set of states. Once the conversion is complete, use the "add trap state" functionality to obtain a complete dfa.
• More help is available from the online JFLAP tutorial (click on "Finite Automata", then "Convert to DFA").

Optional extension to this minilab: play around with the "minimize dfa" functionality. One very interesting example is the one we tried in Class 5: first create an nfa for the language on {a,b} that accepts any string containing "aaaba". Now convert that nfa to a dfa. Now minimize the resulting dfa. Do you get the same results we got by hand?

Class 7: Monday, February 14

grep minilab

Class 8: Thursday, February 17

Minilab: use JFLAP to convert the regular expression a+(bc)* to a finite automaton, then back to a regexp—what happened? Repeat the whole process, but this time convert your automaton into a dfa and minimize it before converting back to a regexp. Experiment with more complex regular expressions.

Class 9: Monday, February 21

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: Thursday, February 24

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: Monday, February 28

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

Class 12: Thursday, March 03

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: Monday, March 07

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

Minilab if time: try as many examples as possible on the regular pumping lemma. Always select the option "computer goes first", as this mimics your role in proving that a language isn't regular.

Class 14: Thursday, March 10

Class 15: Monday, March 21

minilab: Try out a few of the pumping lemma examples on JFLAP. Until you have a good understanding of how the game works, always select the option "computer goes first", as this mimics your role in proving that a language isn't regular. Once you have tried that a few times, you can amplify your understanding by choosing to go first yourself, thus playing the role of the opponent in a typical proof that the language isn't regular.

Class 16: Thursday, March 24

Required reading: Linz 5.1, 5.2. Section 5.3 is optional but interesting, and therefore recommended. Also, you can skip the following topics from Section 5.2, which will not be covered in this course: s-grammar (definition 5.4 and example 5.9); inherently ambiguous grammars (definition 5.6 and example 5.13)

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: Monday, March 28

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: Thursday, March 31

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

Class 19: Monday, April 4

minilab: 1. (if didn't already do 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. continue work on the minilab from class 16.

Class 20: Thursday, April 7

Class 21: Monday, April 11

Class 22: Thursday, April 14

Class 23: Monday, April 18

Minilab:

• Download the Universal Turing machine of Lucas and Jarvis (see also their explanatory webpage if you're interested).
• Encode your binary incrementor machine (or use mine) 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: Thursday, April 21

Main thing to think about from today's class: recall our five running examples of interesting languages (Java programs, HTML pages, multiples of 5, prime numbers, Java programs that can't crash), and add to this list a 6th important example, which is just the complement of number 5: Java programs that can crash. Of these six languages, which ones are recursively enumerable? Which ones are recursive?

Class 25: Monday, April 25

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: Thursday, April 28

Lecture notes on undecidability are available.

Class 27: Monday, May 02

Class 28: Thursday, May 05

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