{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f2\fmodern\fcharset0\fprq1{\*\panose 02070309020205020404}Courier New;}}{\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\adjustright \fs20\cgrid \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright 
\fs20\cgrid \sbasedon0 \snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid \sbasedon0 \snext16 footer;}{\*\cs17 \additive \sbasedon10 page number;}{\s18\widctlpar\adjustright \cgrid \sbasedon0 \snext18 Body Text;}}{\info
{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Tuttle}{\creatim\yr2000\mo4\dy14\hr15\min35}{\revtim\yr2000\mo4\dy14\hr15\min35}{\printim\yr2000\mo4\dy14\hr11\min56}{\version2}{\edmins1}{\nofpages4}{\nofwords1275}{\nofchars7271}
{\*\company CNRS - HSU}{\nofcharsws8929}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale75\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640\adjustright 
\fs20\cgrid {\fs18 CIS 480 - Test 2 Review Notes\tab \tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 4}}}{\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 \widctlpar\adjustright \fs20\cgrid {\b\fs24 Test 2 Review Notes}{\fs24 
\par 
\par *   }{\b\fs24 Test 2}{\fs24  covers material from chapters 1-5 of Sipser, with an emphasis on chapters 2-5. 
\par         *   note that while there will not be the emphasis on reading and writing actual FA's 
\par         and RE's that there was on Test 1, the concepts of how the class of regular languages 
\par         "fits" in relation to other classes of languages is very much a part of the material 
\par         being tested on Test 2. 
\par 
\par         *   Reasoning about regular expressions (RE's), finite automata (FA's), (for example, 
\par         is the problem A}{\fs24\sub DFA}{\fs24  decidable?) is also important.
\par \line Remember:
\par *   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 }{\b\fs24 
\par }{\fs24 *   look at the kinds of questions that were on the HW's --- similar questions are definitely possible on the test.
\par }{\b\fs24 
\par }{\fs24 *   }{\b\fs24 CHAPTER 2 - Context-Free Languages (CFL's)
\par 
\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 
\par         *   in what kind of studies were they first used? they are often used in the 
\par         specification of what?
\par }{\b\fs24 
\par         }{\fs24 *   be able to read, write CFG's, and answer questions about them
\par 
\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 
\par         *   how can you generate a string using a CFG?
\par 
\par }{\b\fs24         }{\fs24 *   what is the language associated with a CFG?
\par 
\par }{\b\fs24         }{\fs24 *   what is a }{\b\fs24 derivation}{\fs24 ? Be able to give one for a given CFG;
\par 
\par }{\b\fs24         }{\fs24 *   what is a }{\b\fs24 parse tree/derivation tree}{\fs24 ? Be able to give one for a given CFG;
\par }{\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 finite automata (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 
\par }{\b\fs24         }{\fs24 *   basically, how does a PDA work?
\par 
\par }{\b\fs24         }{\fs24 *   be comfortable with the formal definition of a PDA;
\par 
\par         *   be comfortable with the PDA handout given out, and be able to write/read PDA 
\par         instantaneous descriptions (ID's); given a PDA and a string, could you use ID's to 
\par         give a derivation for that string, and tell if it was accepted or not? Given the current 
\par         state of a PDA on a string, you should be able to tell what the next few moves would 
\par         be (expressed as ID's).
\par 
\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 
\par         *   is there a pumping lemma for CFL's? What can it be used for?
\par }{\b\fs24 
\par }{\fs24 *   }{\b\fs24 CHAPTER 3 - The Church-Turing Thesis
\par 
\par         }{\fs24 *   TURING MACHINES (TM's)
\par         *   what are they? how do they "work"? when are they said to accept a string? to 
\par         reject a string? what do we mean when we say we do not know whether it will halt?
\par 
\par         *   what is the language associated with a TM?
\par 
\par         *   what classes of languages do they accept?
\par 
\par         *   what is a decider? what class of languages is related to TM's that are deciders?
\par 
\par         *   be comfortable with the formal 7-tuple notation for TM's; be able to read, write, 
\par         reason about TM's, and answer questions about them.
\par 
\par }{\b\fs24         }{\fs24 *   given a TM, and a string, be able to give ID's for the derivation of that string; 
\par         how do you know, from a derivation, if a string has been accepted from the TM or 
\par         not? Give the current state of a TM on a string, you should be able to tell what the 
\par         next few moves would be (expressed as ID's).
\par 
\par }{\b\fs24         }{\fs24 *   why do we say that the TM model is }{\b\fs24 robust}{\fs24 ?
\par 
\par         *   be familiar with some of the common TM variations, and whether those 
\par         variations affect what class of languages is accepted by those TM variations;
\par }{\b\fs24 
\par         }{\fs24 *   THE CHURCH-TURING THESIS
\par         *   what is this?
\par 
\par         *   what two concepts are theorized to be equivalent, according to this? (what 
\par         concept, and what mathematical object?)
\par                 *   the concept: }{\b\fs24 algorithm
\par                 }{\fs24 *   the mathematical object: }{\b\fs24 a Turing Machine }{\b\fs24\ul that halts on all inputs}{\fs24\ul 
\par 
\par }\pard\plain \s18\widctlpar\adjustright \cgrid                 *   (the "\'85that halts on all inputs" restriction is IMPORTANT, note!)
\par \pard\plain \widctlpar\adjustright \fs20\cgrid {\fs24 
\par }{\b\fs24         }{\fs24 *   what are some of the consequences/conclusions from this?
\par }{\b\fs24 
\par }{\fs24 *   }{\b\fs24 CHAPTER 4 - Decidability
\par         }{\fs24 *   what is a problem? Given a problem, can you state its corresponding language?
\par 
\par         *   what does it mean for a problem to be decidable? undecidable? what are the 
\par         implications of its being decidable, undecidable?
\par 
\par }{\b\fs24         }{\fs24 *   how can you prove that a problem is decidable? undecidable?
\par 
\par }{\b\fs24         }{\fs24 *   you should be able to write TM's using the high-level "format" used in this 
\par         chapter and the next;
\par }{\b\fs24 
\par         }{\fs24 *   what was the first problem that the text showed to be undecidable? What 
\par         technique did it use to do so?
\par }{\b\fs24 
\par }{\fs24 *   }{\b\fs24 CHAPTER 5 - Reducibility
\par         }{\fs24 *   what does it mean if problem A reduces to problem B? What does it imply, if 
\par         anything, about problem A? about problem B?
\par }{\b\fs24 
\par         }{\fs24 *   what is reduction? How can you use reduction to prove a problem decidable? to 
\par         prove it undecidable?
\par }{\b\fs24 
\par         }{\fs24 *   you will very likely have to use reduction to prove that a problem is undecidable. 
\par         Note that a version of the reduction template will be provided along with the test. A 
\par         listing of "known" undecidable problems may be included with the reference 
\par         material for the test, also.
\par }{\b\fs24 
\par }{\fs24 *   }{\b\fs24 OTHER
\par 
\par }\pard\plain \s18\widctlpar\adjustright \cgrid *   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. 
\par \pard\plain \widctlpar\adjustright \fs20\cgrid {\fs24         *   I will very likely ask questions to let me see if this is indeed the case;
\par         *   I could ask various questions about how you can determine that a language is a 
\par         member of one of these classes (If a CFG generates it, at least what class is it in? 
\par         etc.)
\par         *   I could also turn this around --- have you tell me how you could/would prove that 
\par         a language is a member of one of these classes;
\par 
\par *   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?
\par 
\par *   we talked about three possibilities for a pair of languages that are complements of one another --- 
\par }\pard \li720\ri720\widctlpar\adjustright {\fs24  Let F and G be a pair of complementary languages. Then }{\b\fs24 either}{\fs24   (1) both F and G are Turing-decidable, (2) neither F nor G are}{\b\fs24  }{\fs24 
Turing-recognizable, or (3) one of F and G is Turing-recognizable but not Turing-decidable; the other is not Turing-recognizable.
\par }\pard\plain \s18\widctlpar\adjustright \cgrid 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. 
\par 
\par *   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?
\par 
\par *   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;
\par 
\par *   attempt at the "language layers" drawing from the board:
\par {\f2\fs20    ----------------------------------------
\par    |\tab \tab \tab Turing-recognizable      |
\par   |                    languages            |
\par  |     -------------------------------       |
\par  |    |      Turing-decidable         |       |
\par  |   |        languages                |      |
\par  |  |    ------------------------       |     | 
\par  |  |    |          Context-free |       |    |
\par  |  |   |            languages    |      |    |
\par  |  |  |    ----------             |     |    |
\par  |  |  |   | Regular  |            |     |    |
\par  |  |  |  | languages  |           |     |    |
\par  |  |   |  |          |           |     |     |
\par   |  |    |  ----------           |     |    |
\par    |  |   -------------------------    |    |
\par     |  --------------------------------    |
\par      --------------------------------------
\par }}