Computer Science 456/656
Automata and Formal Languages
CSC 456/656 Study Guide for the Second
Midterm Examination Spring 2007 April 12
The best way to study is to look at
Study guides and tests of past semesters.
If any topic on those study guides was not yet covered, it will
not be on the exam. In addition:
-
Review your homework assignments.
-
Review the topics covered in the lectures.
-
There will be true/false questions.
-
There will be some definitions
and fill-in-the-blank questions.
-
I will definitely have a question involving parsers.
-
You will need to state the Church-Turing thesis, and explain its importance.
-
I will possibly ask you to explain how a Turing Machine can emulate some
other machine. For example, how can a TM emulate a stack machine?
A machine with two tapes? I would want answers with pictures.
-
I may ask you to state the pumping lemma for context-free languages. If you
write down all the words, but in the wrong order, you might get no partial
credit, because the order of the words in the definition is critical.
-
I will expect you to know how to prove that a language can be enumerated
in canonical form by a machine if and only if some TM accepts it.
-
I will expect you to know the process by which a language is proved to
be NP-complete, given that some other language is known to be NP-complete.
-
Study guides and tests from Previous Semesters