{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f3\froman\fcharset2\fprq2{\*\panose 05050102010706020507}Symbol;}}{\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;}{\s1\qc\keepn\widctlpar\adjustright \b\fs20\cgrid \sbasedon0 \snext0 heading 1;}{\*\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;}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Tuttle}{\creatim\yr2000\mo3\dy29\hr11\min53}{\revtim\yr2000\mo3\dy29\hr11\min53}{\printim\yr1999\mo3\dy10\hr11\min37}{\version2}{\edmins0}{\nofpages1}{\nofwords534}
{\nofchars3046}{\*\company CNRS - HSU}{\nofcharsws3740}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale100\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar
\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 CIS 480 - Homework #6\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 \s1\qc\keepn\widctlpar\outlinelevel0\adjustright \b\fs20\cgrid {CIS 480 - Computer Theory - Spring 2000
\par }\pard\plain \qc\widctlpar\adjustright \fs20\cgrid {\b HOMEWORK #6
\par DUE: Wednesday, April 5th, Beginning of Class}{\b\fs24 
\par }\pard \widctlpar\adjustright {\b 
\par }{If you think you can clearly type your responses in ASCII, you may e-mail this in --- otherwise, turn it in on-paper.
\par }{\b 
\par }\pard \fi-360\li360\widctlpar\adjustright {1.\tab For each of the following }{\b languages}{, state the problem that the language is representing.
\par \tab (a) ALL}{\sub DFA }{= \{<A> | A is a DFA that recognizes }{{\field{\*\fldinst SYMBOL 83 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{*\}
\par 
\par \tab (b) INFINITE}{\sub CFG }{= \{<G> | L(G) is an infinite language\}
\par 
\par \tab (c) SUB = \{<M, N> | M and N are TM's and L(M) }{{\field{\*\fldinst SYMBOL 204 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ L(N)\}
\par }\pard \widctlpar\adjustright {
\par }\pard \fi-360\li360\widctlpar\adjustright {2.\tab For each of the following }{\b problems}{, give a }{\b language}{ that can represent the problem.
\par \tab (a) Does a TM accept the empty string (}{{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{)?
\par 
\par \tab (b) Are a CFG and PDA equivalent? (Is the language generated by a CFG the same as that accepted by a PDA?)
\par 
\par \tab (c) Does a PDA accept any strings?
\par }\pard \widctlpar\adjustright {
\par 3.   You sketch out a nondeterministic Turing machine that can }{\b accept}{ a language }{\b D}{. 
\par 
\par         (a)   In what class of languages can you now reasonably say that }{\b D}{ belongs?
\par }{\b 
\par         }{(b)   It turns out that there is a }{\b problem P}{ corresponding to this language }{\b D}{. Given what you know  
\par         about }{\b D}{, what can you say about }{\b P}{? (I can think of several reasonable answers to this question\'85 you 
\par         only need to give one.)
\par }{\b 
\par }{4.   You sketch out a multitape Turing machine, guaranteed to halt on all possible inputs, that can accept a language }{\b E}{. 
\par 
\par         (a)   In what class of languages can you now reasonably say that }{\b E}{ belongs?
\par }{\b 
\par         }{(b)   It turns out there is a }{\b problem Q}{ corresponding to this language }{\b E}{. Given what you know about 
\par }{\b         E}{, what can you say about }{\b Q}{? (I can think of several reasonable answers to this question\'85you only 
\par         need to give one.)}{\b 
\par }{
\par }{\b 
\par }{\fs24 
\par }}