Challenge Problems in Automata and Formal Languages

Revised January 24, 2023.

Turn in your solution to one of these problems directly to Dr. Larmore (not the teaching assistant) by Wednesday, April 26. The purpose of these problems is to provide a challenge to the top students, meaning those who master the regular material of the course and would like to learn more.
Do not try to work these problems to improve a poor grade ... if you are doing badly in the course, concentrate on the regular material.
  1. Do both parts below.
    1. Give a polynomial time reduction of 5-SAT to 3-SAT. (Do not use, or refer to, the polynomial time reduction of SAT to 3-SAT.)
    2. Prove that 2-SAT is polynomial time.

  2. Do both parts below.
    1. Prove Properties 1, 2, and 3 in the file Recursive real numbers
    2. Prove Property 4 in the same file.

  3. Any NFA with n states is equivalent to a minimal DFA with no more than 2n states. Prove that, for any n, there is an NFA with n states which is equivalent to a minimal DFA with exactly 2n states.