Computer Science 456/656
Automata and Formal Languages
CSC 456/656 Study Guide for Final Examination
Finished
-
There will be true/false questions. Some of these
will be on the final exam.
-
There will be one question involving construction or minimization
of finite automata.
-
There may be a question involving regular expressions.
-
There will be some definitions and fill-in-the-blank questions.
-
There will be a question involving constructing a CF grammar for a language.
-
There will be a
question requiring the use of the pumping lemma for
context-free languages to prove that some particular language is not
context-free.
-
I will expect you to know what the universal language
(also known as the halting problem) is, as well as the
fact that it's undecidable, i.e., not recursive, and that it is recursively
enumerable.
-
I expect you to know what the Church Turing thesis is,
and why it's important.
-
At least one homework problem that was assigned during the semester will
appear on the final.