The first part of the course will provide some basic elements of Formal Language Theory, including Finite State Machines (fsm) and Recursive Function Theory. Note that fsm is part of your required background, so we view this part as training in writing rigorous proofs. We will use Sipser's book for the first part.