{\rtf1\ansi \deff4\deflang1033{\fonttbl{\f4\froman\fcharset0\fprq2 Times New Roman;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;
\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\widctlpar 
\f4\fs20 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext16 footer;}{\*\cs17 \additive\sbasedon10 
page number;}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Sharon M. Tuttle}{\creatim\yr2000\mo2\dy12\min25}{\revtim\yr2000\mo2\dy12\hr19\min44}{\printim\yr1998\mo9\dy21\hr12\min48}{\version9}{\edmins41}{\nofpages3}
{\nofwords1029}{\nofchars5867}{\*\company CNRS - HSU}{\vern57431}}\widowctrl\ftnbj\aenddoc\formshade \fet0\sectd \linex0\endnhere {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 {\fs18 CIS 480 - Test 1 Review Notes\tab \tab p. }
{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 1}}}{\fs18 
\par Sharon Tuttle - Spring 2000
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \qc\widctlpar \f4\fs20 {\b HUMBOLDT STATE UNIVERSITY
\par CIS 480 - Computer Theory
\par Spring Semester - 2000}{\b\fs24 
\par }\pard \qc\widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 Test 1 Review Notes}{\fs24 
\par 
\par }\pard \widctlpar {\fs24 *   }{\b\fs24 Test 1}{\fs24  covers material only from Chapters 0-2 of Sipser, and mostly chapters 1-2.
\par }\pard \widctlpar {\fs24         *   Chapter 0's basics appear as needed within the Chapter 1- and 2-oriented 
\par }\pard \widctlpar {\fs24         questions; they are unlikely to be the }{\b\fs24 focus}{\fs24  of questions;
\par }\pard \widctlpar {\fs24    
\par }\pard \widctlpar {\fs24 *   if it was on the homework, it is fair game;
\par *   if we discussed it in class, it is fair game;
\par *   if it was in the reading and we "skipped" it, DON'T WORRY about that;
\par *   if it was in the reading and we discussed that topic, it is fair game;
\par }\pard \widctlpar {\b 
\par }\pard \widctlpar {\fs24 *   (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;)
\par }\pard \widctlpar {\b 
\par }\pard \widctlpar {\fs24 *   reminder of "traditional" pumping lemma gaffes:}{\b\fs24 
\par }{\fs24         *   please note: in pumping lemma proofs,
\par }{\b\fs24                 }{\fs24 *   you get to assume an n exists (a pumping length n exists), and then
\par }{\b\fs24                 }{\fs24 *   YOU get to pick ANY string of at least that length, accepted by the 
\par                 language;
\par 
\par                 *   BUT NOTE --- you cannot pick just ONE POSSIBLE partitioning of that 
\par                 string uvw --- we have to then show that NO POSSIBLE partitioning uvw 
\par                 exists such that u(v^i)w is also in the language;
\par                         *   (this is NOT permitted:  "here's A partition 
\par                         of my chosen string that cannot be pumped"; NO; you've got to show that 
\par                         NO partition will work, of ALL possible partitions into uvw;)
\par }{\b\fs24 
\par }\pard \widctlpar {\fs24 *   }{\b\fs24 CHAPTER 1}{\fs24  }{\b\fs24 - Regular Languages
\par }\pard \widctlpar {\fs24 
\par         *   Deterministic Finite Automata
\par }{\b\fs24                 }{\fs24 *   what are they? 
\par                 *   What are "restrictions" on them?
\par                         *   must have exactly 1 transition from each node for every possible input;
\par }\pard \widctlpar {\fs24                 *   be comfortable with }{\b\fs24 state diagrams/transition diagrams}{\fs24  for DFA's;
\par }\pard \widctlpar {\fs24                         *   be sure to indicate }{\b\fs24 start}{\fs24  state with an arrow, and }{\b\fs24 accept states/final 
\par                         states}{\fs24  with a double-circle;
\par }\pard \widctlpar {\fs24                 *   what is the language associated with a DFA?
\par 
\par }\pard \widctlpar {\fs24                 *   }{\b\fs24 Q EX.: }{\fs24 Given a particular DFA, be able to tell if a given string is 
\par }\pard \widctlpar {\fs24                 ACCEPTED by that DFA or not;
\par }\pard \widctlpar {\fs24                 *   }{\b\fs24 Q EX.: }{\fs24 Given a description of a simple regular language (could be as prose, 
\par }\pard \widctlpar {\fs24                 or as a regular expression, etc.), draw a transition diagram for a DFA that 
\par                 accepts that language;
\par }\pard \widctlpar {\fs24                 *   }{\b\fs24 Q EX.}{\fs24 : Given a DFA in 5-tuple form (Q, alphabet, delta, start state, F), draw 
\par }\pard \widctlpar {\fs24                 a corresponding transition diagram.
\par }\pard \widctlpar {\fs24                 *   }{\b\fs24 Q EX.}{\fs24 : Given a transition diagram, draw the corresponding 5-tuple;
\par }\pard \widctlpar {\b\fs24 
\par         }{\fs24 *   be comfortable with 5-tuple "formal" FA definition;
\par }{\b\fs24         }{\fs24 *   what's the difference between a DFA and a NFA?
\par                 *   given a transition diagram, could you tell if it was a DFA or an NFA?
\par                 *   given a 5-tuple, could you tell if it was a DFA or an NFA?
\par         *   what does "nondeterminism" mean, in terms of FA's?
\par         *   what is an epsilon-move?
\par }{\b\fs24         }{\fs24 *   be able to READ NFA's (with and without epsilon moves)
\par                 *   be able to write the "tree of possibilities" for an NFA
\par                 *   what does it mean for an NFA to accept a string? WHEN is an NFA said to 
\par                 accept a string? what is the language associated with an NFA?
\par }{\b\fs24         }{\fs24 *   EQUIVALENCE of NFA's and DFA's
\par         *   (note --- the term FA is assumed to encompass both NFA's and DFA's)
\par }{\b\fs24 
\par         }{\fs24 *   what are the regular operations? What does it mean, that the class of regular 
\par         languages is closed under these regular operations? How can one then use the 
\par         regular operations in proving some languages regular?}{\b\fs24 
\par 
\par         }{\fs24 *   REGULAR EXPRESSIONS
\par         *   what is a R.E.? What does it do? (describes a regular language!)
\par                 *   what are concatenation, union, star?
\par                 *   how are regular expressions built using these operations on languages?
\par }{\b\fs24         }{\fs24 *   be able to READ them, WRITE them
\par }{\b\fs24         }{\fs24 *   be able to tell if a string is a member of the language described by a RE
\par }{\b\fs24         }{\fs24 *   EQUIVALENCE of RE's, FA's
\par }{\b\fs24                 }{\fs24 *   (I would expect you to understand the proof of how there is an FA accepting 
\par                 every RE --- that's the nifty induction proof with the diagrams;)
\par 
\par         * what are some ways FA's can be used? Why/when can FA's be useful?
\par 
\par         *   pumping lemma
\par                 *   using pumping lemma to prove langs are not regular
\par 
\par         *   note too --- can show a lang is regular by\'85
\par                 *   developing ANY FA for it;
\par                 *   writing an RE for it;
\par                 *   showing it's the result of a closure op with another regular set;
\par 
\par }\pard \widctlpar {\fs24 
*   (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 su
re with what's given\'85)
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\fs24 *   }{\b\fs24 CHAPTER 2 - Context-Free Languages
\par }\pard \widctlpar {\b\fs24 
\par         }{\fs24 *   how do these differ from regular languages, in general? how are they related to 
\par         regular languages? 
\par 
\par         *   CONTEXT-FREE GRAMMARS (CFG's)
\par         *   how can they be used to generate languages? what class of languages do they 
\par         generate?
\par         *   in what kind of studies were they first used? they are often used in the 
\par         specification of what?}{\b\fs24 
\par         }{\fs24 *   be able to read, write CFG's, and answer questions about them
\par }{\b\fs24         }{\fs24 *   variables/nonterminals, terminals, start variable/start nonterminal, production 
\par         rules/substitution rules --- what are they, can you recognize them in a given CFG?
\par         *   how can you generate a string using a CFG?
\par }{\b\fs24         }{\fs24 *   what is the language associated with a CFG?
\par }\pard \widctlpar {\b\fs24         }{\fs24 *   what is a }{\b\fs24 derivation}{\fs24 ? Be able to give one for a given CFG;
\par }{\b\fs24         }{\fs24 *   what is a }{\b\fs24 parse tree/derivation tree}{\fs24 ? Be able to give one for a given CFG;
\par }\pard \widctlpar {\b\fs24         }{\fs24 *   be comfortable with the formal definition of a CFG
\par }{\b\fs24 
\par         }{\fs24 *   what does it mean for a CFG to be ambiguous? How can you prove a CFG is 
\par         ambiguous? What is a leftmost derivation?
\par 
\par         *   PUSHDOWN AUTOMATA (PDA)
\par }{\b\fs24         }{\fs24 *   what are they? How do they differ from FA's? 
\par }{\b\fs24         }{\fs24 *   if a language is accepted by a PDA, what does that imply about the existence of a 
\par         CFG for that language? Of what class of languages does that mean that language is a 
\par         member?
\par                 *   can you prove that all regular languages are context-free, using PDA's?
\par }{\b\fs24         }{\fs24 *   basically, how does a PDA work?
\par }{\b\fs24         }{\fs24 *   be comfortable with the formal definition of a PDA;
\par         *   be comfortable with the PDA handout given out, and be able to write/read PDA 
\par         instantaneous descriptions (ID's)
\par }{\b\fs24         }{\fs24 *   PDA's are nondeterministic --- consider the subset of PDA's that happen to be 
\par         deterministic. Are they equivalent in terms of languages accepted to PDA's in 
\par         general?
\par }\pard \widctlpar {\fs24 
\par }\pard \widctlpar {\fs24         *   is there a pumping lemma for CFL's? What can it be used for?
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 
\par }}