Please send questions to
st10@axe.humboldt.edu .
HUMBOLDT STATE UNIVERSITY
CIS 480 - Computer Theory
Spring Semester - 2000
Test 1 Review Notes
* Test 1 covers material only from Chapters 0-2 of Sipser, and mostly
chapters 1-2.
* Chapter 0's basics appear as needed within the Chapter 1- and
2-oriented
questions; they are unlikely to be the focus of questions;
* 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;
* (and, because of the still-"beta" nature of this course, I'll give
you a bit more idea than I normally would what sort of questions to expect;)
* reminder of "traditional" pumping lemma gaffes:
* please note: in pumping lemma proofs,
* you get to assume an n exists (a pumping length n
exists), and then
* YOU get to pick ANY string of at least that length,
accepted by the
language;
* BUT NOTE --- you cannot pick just ONE POSSIBLE
partitioning of that
string uvw --- we have to then show that NO POSSIBLE
partitioning uvw
exists such that u(v^i)w is also in the language;
* (this is NOT permitted: "here's A partition
of my chosen string that cannot be pumped"; NO;
you've got to show that
NO partition will work, of ALL possible
partitions into uvw;)
* CHAPTER 1 - Regular Languages
* Deterministic Finite Automata
* what are they?
* What are "restrictions" on them?
* must have exactly 1 transition from each node
for every possible input;
* be comfortable with state diagrams/transition
diagrams for DFA's;
* be sure to indicate start state with an
arrow, and accept states/final
states with a double-circle;
* what is the language associated with a DFA?
* Q EX.: Given a particular DFA, be able to tell if a
given string is
ACCEPTED by that DFA or not;
* Q EX.: Given a description of a simple regular
language (could be as prose,
or as a regular expression, etc.), draw a transition
diagram for a DFA that
accepts that language;
* Q EX.: Given a DFA in 5-tuple form (Q, alphabet,
delta, start state, F), draw
a corresponding transition diagram.
* Q EX.: Given a transition diagram, draw the
corresponding 5-tuple;
* be comfortable with 5-tuple "formal" FA definition;
* what's the difference between a DFA and a NFA?
* given a transition diagram, could you tell if it was
a DFA or an NFA?
* given a 5-tuple, could you tell if it was a DFA or an
NFA?
* what does "nondeterminism" mean, in terms of FA's?
* what is an epsilon-move?
* be able to READ NFA's (with and without epsilon moves)
* be able to write the "tree of possibilities" for an NFA
* what does it mean for an NFA to accept a string? WHEN
is an NFA said to
accept a string? what is the language associated with an NFA?
* EQUIVALENCE of NFA's and DFA's
* (note --- the term FA is assumed to encompass both NFA's and
DFA's)
* what are the regular operations? What does it mean, that the
class of regular
languages is closed under these regular operations? How can one
then use the
regular operations in proving some languages regular?
* REGULAR EXPRESSIONS
* what is a R.E.? What does it do? (describes a regular language!)
* what are concatenation, union, star?
* how are regular expressions built using these
operations on languages?
* be able to READ them, WRITE them
* be able to tell if a string is a member of the language
described by a RE
* EQUIVALENCE of RE's, FA's
* (I would expect you to understand the proof of how
there is an FA accepting
every RE --- that's the nifty induction proof with the
diagrams;)
* what are some ways FA's can be used? Why/when can FA's be useful?
* pumping lemma
* using pumping lemma to prove langs are not regular
* note too --- can show a lang is regular by
* developing ANY FA for it;
* writing an RE for it;
* showing it's the result of a closure op with another
regular set;
* (do note, then --- you have a VARIETY of ways of telling if a
language is regular or not; be familiar with them! I could give
scenarios, and ask if you know that the language in that scenario is
regular, not regular, or you can't be sure with what's given)
* CHAPTER 2 - Context-Free Languages
* 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 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)
* 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?