Computer Science 456/656
Automata and Formal Languages
CSC 456/656 Study Guide for the Second
Midterm Examination Fall 2006 October 31
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.
-
There may be a question that is very hard, that most students will not
be able to answer, in order to challenge the top students.
-
Study guides and tests from Previous Semesters