{\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;}{
\s2\keepn\widctlpar\outlinelevel1\adjustright \b\fs20\cgrid \sbasedon0 \snext0 heading 2;}{\*\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\dy20\hr11\min39}
{\revtim\yr2000\mo3\dy20\hr11\min45}{\printim\yr1999\mo3\dy10\hr11\min37}{\version3}{\edmins1}{\nofpages2}{\nofwords464}{\nofchars2647}{\*\company CNRS - HSU}{\nofcharsws3250}{\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 #5\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 #5
\par DUE: Wednesday, March 29th, Beginning of Class}{\b\fs24 
\par }\pard \widctlpar\adjustright {
\par You may turn this in either by e-mail or on-paper.
\par 
\par }\pard\plain \s2\keepn\widctlpar\outlinelevel1\adjustright \b\fs20\cgrid CFG's
\par \pard\plain \fi-360\li360\widctlpar\adjustright \fs20\cgrid {1. \tab Show that the following grammar is ambiguous:
\par }\pard \widctlpar\adjustright {        S --> AB | aaB
\par         A --> a | Aa
\par         B --> b
\par }{\b 
\par }\pard\plain \s2\keepn\widctlpar\outlinelevel1\adjustright \b\fs20\cgrid PDA's
\par \pard\plain \widctlpar\adjustright \fs20\cgrid {Consider the following pushdown automaton (PDA) M:
\par \tab M = (\{q}{\sub 0}{, q}{\sub 1}{, q}{\sub 2}{, q}{\sub 3}{\}, \{0, 1\}, \{Z, X\}, }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{, q}{\sub 0}{, \{q}{\sub 3}{\} )}{\fs24 
\par }{\tab with }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ given by:
\par }\pard \fi720\li720\widctlpar\adjustright {{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 0}{, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{) = \{ (q}{\sub 1}{, Z) \}
\par }\pard \widctlpar\adjustright {\tab \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 1}{, 1, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{) = \{ (q}{\sub 1}{, X) \}}{\fs24 
\par }{\tab \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 1}{, 0, X) = \{ (q}{\sub 2}{, X) \}}{\fs24 
\par }{\tab \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 1}{, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{, Z) = \{ (q}{\sub 3}{, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{) \}}{\fs24 
\par }{\tab \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 2}{, 1, X) = \{ (q}{\sub 2}{, }{{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{) \}}{\fs24 
\par }{\tab \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 2}{, 0, Z) = \{ (q}{\sub 1}{, Z) \}
\par 
\par Consider the string }{\b 110110}{. At some point in the operation of M, above, you have the instantaneous description (ID) }{\b (q}{\b\sub 1}{\b , 0110, XXZ)}{. 
\par 
\par }\pard \fi-360\li360\widctlpar\adjustright {2.\tab What will be the }{\b instantaneous ID}{ resulting after the next move?
\par }\pard \widctlpar\adjustright {
\par }\pard \fi-360\li360\widctlpar\adjustright {3. \tab What will be the }{\b instantaneous ID}{ resulting after the move after #1's move?
\par }\pard \widctlpar\adjustright {
\par }\pard \fi-360\li360\widctlpar\adjustright {4.\tab Will the string }{\b 110110}{ be accepted by this PDA? To answer this, give the sequence of ID's (separated by |--, as shown in the PDA handout) that shows whether it is accepted or not, and then }{\b 
also}{ tell how this shows that this string is accepted or not. (Note that a sequence of PDA ID's separated by |-- is a kind of derivation, also.)
\par }\pard \widctlpar\adjustright {
\par }\pard \fi-360\li360\widctlpar\adjustright {5.\tab Give another derivation (using |-- notation, with instantaneous descriptions (ID's)) for any string accepted by this PDA. How do you know it has been accepted?
\par }\pard \widctlpar\adjustright {
\par }\pard \fi-360\li360\widctlpar\adjustright {6.\tab Give another derivation for a string containing at least 5 symbols that would }{\b not}{ be accepted by this PDA M. How do you know it has been rejected?}{\fs24 
\par }\pard \widctlpar\adjustright {\b 
\par }\pard\plain \s2\keepn\widctlpar\outlinelevel1\adjustright \b\fs20\cgrid Turing Machines
\par \pard\plain \widctlpar\adjustright \fs20\cgrid {7.   Assume that you have a Turing machine }{\b M}{, which includes set of input symbols }{{\field{\*\fldinst SYMBOL 229 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ = \{0, 1\} and set of states Q = \{ q}{\sub 
0}{, q}{\sub 1}{, q}{\sub 2}{, q}{\sub 3}{ \}. Currently, this TM }{\b M}{ has the instantaneous description (ID) }{\b 0011q}{\b\sub 1}{\b 0011.
\par 
\par }{A }{\b portion}{ of the next move function }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ is:
\par         }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 1}{, 0 ) = (q}{\sub 2}{, 0, L)
\par         }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 1}{, 1 ) = (q}{\sub 1}{, 0, R)
\par }{\b         }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 2}{, 0 ) = (q}{\sub 2}{, 0, R)
\par         }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{( q}{\sub 2}{, 1 ) = (q}{\sub 1}{, 0, L)}{\b 
\par 
\par         }{(a)   After the }{\b next move}{, what will be the resulting ID?
\par }{\b 
\par }{        (b)   And, after the move after that, what will be the resulting ID?
\par }{\b 
\par }{8.   You have a }{\b Turing-recognizable}{ }{\b language}{ }{\b B}{, and Turing machine }{\b M}{ happens to accept }{\b B}{ (that is, }{\b L(M) = B}{).
\par }{\b         }{(a)   You start out }{\b M}{ on an input string }{\b w}{, and M has not stopped yet. Assume that you do }{\b not}{ know if 
\par }{\b         w }{is an element of }{\b B}{ or not. Can you guarantee that }{\b M}{ will eventually halt? Why or why not?
\par 
\par         (b)   You start out }{\b M}{ on an input string }{\b x}{, and M has not stopped yet. Assume that you }{\b know}{ that }{\b x}{ is 
\par         an element of }{\b B}{. Can you guarantee that }{\b M}{ will eventually halt? Why or why not?}{\b 
\par 
\par }{9.   You have a }{\b Turing-decidable}{ }{\b language C}{, and Turing machine }{\b N}{ happens to accept }{\b C}{ (that is, }{\b L(N) = C}{). You are told, however, that N does not halt for }{\b some}{ inputs that are not members of }{\b C}{
. How can this be?
\par }{\b 
\par }{10.   What two concepts does the }{\b Church-Turing thesis}{ suggest should be considered equivalent? 
\par 
\par 11.   You sketch out a nondeterministic Turing machine that can }{\b accept}{ a language }{\b D}{. In what class of languages can you now reasonably say that }{\b D}{ belongs? Why?
\par }{\b 
\par }{12.   You sketch out a multitape Turing machine, guaranteed to halt on all possible inputs, that can accept a language }{\b E}{. In what class of languages can you now reasonably say the }{\b E}{ belongs? Why?
\par }{\b 
\par 
\par }{\fs24 
\par }}