CSE 105: Theory of Computation (Spring 2006)

Scores

Scores are available online at Gradesource.

Exam policies

For all exams and quizzes, you may not use books or calculators. One double-sided 8.5x11 page of handwritten notes is allowed for the midterms and final.

Quizzes

The quizzes will be at the beginning of class on Tuesdays and will consist of slight modifications of several of the homework problems assigned for that day, and will cover material discussed through the previous week.

The lowest quiz score is dropped. The remainder are equally weighted and worth a total of 16% of your grade.

Midterm

There will be one midterm worth 35% of your grade.

Here are the things you'll need to be able to know how to do for the midterm:

Given a description of a regular language:
- Write a regular expression for it.
- Write an FSA for it.
Given a regular expression, describe the language.
Given an FSA, describe the language.
Convert an FSA to a regular expression that recognizes the same language.
Convert an NFA to a DFA.
Convert a regular expression to an FSA that recognizes the same language.
Minimize the states in a DFA using the minimization algorithm.
Use the pumping lemma for regular languages to prove a language is not regular.
Use the closure properties of regular languages to prove that a language is not regular.
Given a description of a context-free language:
- Write a context-free grammar for it.
- Write a PDA for it.
Given a CFG, describe the language.
Given a PDA, describe the language.
Convert a CFG to a PDA that recognizes the same language using the algorithm given in class.
Use the pumping lemma for context-free languages to prove a language is not context-free.
Use the closure properties of CFLs to prove that a language is not context-free.
Given a grammar and a string in the grammar, show a leftmost (and rightmost) derivation, and parse tree.
Demonstrate that a given grammar is ambiguous.
Convert a CFG to Chomsky Normal Form.

Here are the things you'll need to know:

Closure properties for regular, deterministic context-free and context-free languages
Examples of languages that are in, and not in, the class of regular, DCFL, and CFL.
Why the pumping lemma is true (the loop in an FSA, or the repetition of states in a parse tree).
Formal definitions and terms for:
- Regular expressions
- DFA
- NFA
- Context-free grammars
- DPDA
- NPDA

Here is the solution to the midterm:

Final

The final will be held on Wednesday, June 14, from 7-10 PM. The final is worth 49% of your grade.

For the final, study the above items that were on the midterm, and the following topics:

State diagrams/ basics of TMs
configurations of TMs
Recognizability
Decidability
closure properties of recognizable and decidable languages.
existence of undecidable languages/ diagonalization
The standard undecidable langauges (Atm, Etm, REGULARtm, EQtm, ...)
Rice's theorem.
Mapping and turing reductions.
PCP problem
P, NP, PSPACE, EXP
Completeness, hardness (especially NP completeness and hardness)
Polynomial time reductions

Regrades

You have the right of appeal for grading on all tests; however, an appeal (except for addition errors) covers the entire test, and may result in an unfavorable judgment on another problem. You have one week from the time the tests are returned to make appeals, including addition errors on your score. Check it over carefully when you get it. Appeals must be made in writing and turned in to Evan.