Please send questions to
st10@axe.humboldt.edu .
Test 2 Review Notes
* Test 2 covers material from chapters 1-5 of Sipser, with an emphasis
on chapters 2-5.
* note that while there will not be the emphasis on reading and
writing actual FA's
and RE's that there was on Test 1, the concepts of how the class
of regular languages
"fits" in relation to other classes of languages is very much a
part of the material
being tested on Test 2.
* Reasoning about regular expressions (RE's), finite automata
(FA's), (for example,
is the problem ADFA decidable?) is also important.
Remember:
* if it was on the homework, it is fair game;
* if we discussed it in class, it is fair game;
* if it was in the reading and we "skipped" it, DON'T WORRY about that;
* if it was in the reading and we discussed that topic, it is fair game;
* look at the kinds of questions that were on the HW's --- similar
questions are definitely possible on the test.
* CHAPTER 2 - Context-Free Languages (CFL's)
* how do these differ from regular languages, in general? how
are they related to
regular languages?
* CONTEXT-FREE GRAMMARS (CFG's)
* how can they be used to generate languages? what class of
languages do they
generate?
* in what kind of studies were they first used? they are often
used in the
specification of what?
* be able to read, write CFG's, and answer questions about them
* variables/nonterminals, terminals, start variable/start
nonterminal, production
rules/substitution rules --- what are they, can you recognize
them in a given CFG?
* how can you generate a string using a CFG?
* what is the language associated with a CFG?
* what is a derivation? Be able to give one for a given CFG;
* what is a parse tree/derivation tree? Be able to give one for
a given CFG;
* be comfortable with the formal definition of a CFG
* what does it mean for a CFG to be ambiguous? How can you
prove a CFG is
ambiguous? What is a leftmost derivation?
* PUSHDOWN AUTOMATA (PDA)
* what are they? How do they differ from finite automata
(FA's)?
* if a language is accepted by a PDA, what does that imply
about the existence of a
CFG for that language? Of what class of languages does that mean
that language is a
member?
* can you prove that all regular languages are
context-free, using PDA's?
* basically, how does a PDA work?
* be comfortable with the formal definition of a PDA;
* be comfortable with the PDA handout given out, and be able to
write/read PDA
instantaneous descriptions (ID's); given a PDA and a string,
could you use ID's to
give a derivation for that string, and tell if it was accepted or
not? Given the current
state of a PDA on a string, you should be able to tell what the
next few moves would
be (expressed as ID's).
* PDA's are nondeterministic --- consider the subset of PDA's
that happen to be
deterministic. Are they equivalent in terms of languages accepted
to PDA's in
general?
* is there a pumping lemma for CFL's? What can it be used for?
* CHAPTER 3 - The Church-Turing Thesis
* TURING MACHINES (TM's)
* what are they? how do they "work"? when are they said to
accept a string? to
reject a string? what do we mean when we say we do not know
whether it will halt?
* what is the language associated with a TM?
* what classes of languages do they accept?
* what is a decider? what class of languages is related to TM's
that are deciders?
* be comfortable with the formal 7-tuple notation for TM's; be
able to read, write,
reason about TM's, and answer questions about them.
* given a TM, and a string, be able to give ID's for the
derivation of that string;
how do you know, from a derivation, if a string has been accepted
from the TM or
not? Give the current state of a TM on a string, you should be
able to tell what the
next few moves would be (expressed as ID's).
* why do we say that the TM model is robust?
* be familiar with some of the common TM variations, and
whether those
variations affect what class of languages is accepted by those TM
variations;
* THE CHURCH-TURING THESIS
* what is this?
* what two concepts are theorized to be equivalent, according
to this? (what
concept, and what mathematical object?)
* the concept: algorithm
* the mathematical object: a Turing Machine that halts
on all inputs
* (the "that halts on all inputs" restriction is
IMPORTANT, note!)
* what are some of the consequences/conclusions from this?
* CHAPTER 4 - Decidability
* what is a problem? Given a problem, can you state its
corresponding language?
* what does it mean for a problem to be decidable? undecidable?
what are the
implications of its being decidable, undecidable?
* how can you prove that a problem is decidable? undecidable?
* you should be able to write TM's using the high-level
"format" used in this
chapter and the next;
* what was the first problem that the text showed to be
undecidable? What
technique did it use to do so?
* CHAPTER 5 - Reducibility
* what does it mean if problem A reduces to problem B? What
does it imply, if
anything, about problem A? about problem B?
* what is reduction? How can you use reduction to prove a
problem decidable? to
prove it undecidable?
* you will very likely have to use reduction to prove that a
problem is undecidable.
Note that a version of the reduction template will be provided
along with the test. A
listing of "known" undecidable problems may be included with the
reference
material for the test, also.
* OTHER
* note, too --- at this point, you should be very comfortable with the
classes of regular languages, CFL,s Turing-decidable languages, and
Turing-recognizable languages.
* I will very likely ask questions to let me see if this is
indeed the case;
* I could ask various questions about how you can determine
that a language is a
member of one of these classes (If a CFG generates it, at least
what class is it in?
etc.)
* I could also turn this around --- have you tell me how you
could/would prove that
a language is a member of one of these classes;
* I am likely to include some questions deliberately combining the
above material in ways that will show if you are really comfortable with
it --- for example, if a language is Turing-decidable, is there
definitely a RE for it? If a problem is undecidable, can you be sure that
there is no PDA accepting it?
* we talked about three possibilities for a pair of languages that are
complements of one another ---
Let F and G be a pair of complementary languages. Then either (1) both
F and G are Turing-decidable, (2) neither F nor G are
Turing-recognizable, or (3) one of F and G is Turing-recognizable but not
Turing-decidable; the other is not Turing-recognizable.
This will be included on the sheet of reference information given with
the test. However, I will expect you to be able to reason about it,
answer questions based on this.
* we talked about Rice's theorem, too, (more in lecture --- it is only
lightly touched on in the text). What does it say? What are its implications?
* I could ask questions about how one could prove that a language is or
is not in one of the language classes, or how we could that a problem is
or is not decidable;
* attempt at the "language layers" drawing from the board:
----------------------------------------
| Turing-recognizable |
| languages |
| ------------------------------- |
| | Turing-decidable | |
| | languages | |
| | ------------------------ | |
| | | Context-free | | |
| | | languages | | |
| | | ---------- | | |
| | | | Regular | | | |
| | | | languages | | | |
| | | | | | | |
| | | ---------- | | |
| | ------------------------- | |
| -------------------------------- |
--------------------------------------