This is summary of the material to study for the test on November 5.
  1. Review all the written homework assignments:
    1. Assignment 1.
    2. Assignment 2.
    3. Assignment 3.
    4. Assignment 4.
    5. Assignment 5.
    6. Assignment 6.
    7. Assignment 7.
    8. Assignment 8.
  2. Review old exams from previous semesters, but remember, there is now a different textbook. Certain material emphasized in prior semesters will not be emphasized this semester, since it is not covered as extensively in our current textbook. For example, I will not be asking detailed questions about parsers. Conversely, material emphasized in our current textbook but not in the previous textbook might be covered more extensively.
  3. Let L be the language of all regular expressions over the alphabet {0,1}.
    1. Give a context-free grammar for L that has only one variable. (This grammar will be ambiguous.)
    2. Give an unambiguous context-free grammer for L such that the parse tree of any regular expression is consistent with the semantics of that expression. Your grammar will need more than one variable.
  4. I expect you to know about Chomsky normal form grammars.
    1. Define Chomsky normal form.
    2. Given a context-free grammar, I might ask you to find an equivalent Chomsky normmal form grammar. What do you do if the empty string is in the language?
  5. Describe a PDA which accepts the language of all palindromes over the alphabet {0,1}. Your description can be either a transition table or a diagram.
  6. Be familiar with the pumping lemma for context-free languages.
    1. Give an accurate statement of the pumping lemma for context-free languages.
    2. Sketch the proof of the pumping lemma for context-free languages.
    3. Use the pumping lemma directly to prove that {anbncn} is not context-free.
    4. Use the pumping lemma directly to prove that the language of all doubled strings over {a,b}, that is, all strings of the form ww where w is any string over {a,b}, is not context-free. Some strings in that language.
  7. What is the Church-Turing Thesis and why do we care so much about it?
  8. Find a general grammar that generates the language of all doubled strings over {a,b}, that is, all strings of the form ww where w is any string over {a,b}.
    1. If you are having trouble, look at Hint 1.
    2. If that doesn't do it, look at Hint 2 Monday morning.
  9. Define:
    1. Recursive function.
    2. Recursive language.
    3. Recursively enumerable language.
    4. Reduction.
    5. The diagonal language. (Called the diagonalization language on page 370 of your textbook.)
    6. The universal language. (See page 377 of your textbook.)
  10. We could say that a machine M writes a real number x if it runs forever, writing all decimal digits of x. For example, a computer running this program writes the number 1/7. (Note that it prints 1.142857142857... without end.)
    1. Suppose x is a rational number. Prove that there is a machine that writes x.
    2. Does there exist a machine that writes the square root of 2? This program is designed for an abstract Pascal machine that has no limit on the size of integer.
    3. Does there exist a machine that writes pi, the well-known ratio of the circumference of a circle to its diameter? Hint.
    4. Is there a real number that cannot be written by any machine? Hint.
    5. What if we say "binary digits" instead of "decimal digits." How does this effect things?
  11. There will be no questions concerning the class of polynomial time languages, or the class of non-deterministic polynomial time languages, on the November 5 test.