{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}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\adjustright \fs20\cgrid \snext0 Normal;}{\s1\qc\keepn\widctlpar\adjustright \b\fs20\cgrid \sbasedon0 \snext0 heading 1;}{\s2\keepn\widctlpar\adjustright \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;}}{\*\listtable{\list\listtemplateid259955080\listsimple{\listlevel\levelnfc0\leveljc0\levelfollow0\levelstartat4\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname 
;}\listid1793740694}}{\*\listoverridetable{\listoverride\listid1793740694\listoverridecount0\ls1}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Tuttle}{\creatim\yr2000\mo4\dy5\hr15\min15}{\revtim\yr2000\mo4\dy5\hr15\min15}
{\printim\yr1999\mo3\dy10\hr11\min37}{\version2}{\edmins0}{\nofpages2}{\nofwords638}{\nofchars3638}{\*\company CNRS - HSU}{\nofcharsws4467}{\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 #7\tab \tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 2}}}{\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 #7
\par DUE: Wednesday, April 12th, Beginning of Class}{\b\fs24 
\par }\pard \widctlpar\adjustright {\b 
\par }{1.   Consider pairs of }{\b complementary}{ languages }{\b F}{ and }{\b G}{. (That is, }{\b F}{ is the complement of }{\b G}{, and vice versa.) (Assume they are a }{\b different}{ pair of languages for each question below\'85)
\par }{\b 
\par         }{(a)   You discover that you can sketch out Turing machines that }{\ul accept}{ }{\b F}{ and }{\b G}{. What is the }{\b strongest}{ 
\par         statement you can now make about the languages }{\b F}{ and }{\b G}{?}{\b 
\par 
\par         }{(b)   You discover that }{\b G}{ is Turing-decidable. What do you now know about }{\b F}{?}{\b 
\par 
\par         }{(c)   You discover that }{\b G}{ is }{\b not}{ Turing-recognizable. What are the possibilities for }{\b F}{?
\par }{\b 
\par Note the following required format (for this class) for showing that a problem is decidable:
\par }\pard \fi-360\li360\widctlpar\adjustright {\b\lang1024 {\shp{\*\shpinst\shpleft-120\shptop0\shpright8400\shpbottom5832\shpfhdr0\shpbxcolumn\shpbypara\shpwr3\shpwrk0\shpfblwtxt0\shpz0\shplid1026
{\sp{\sn shapeType}{\sv 1}}{\sp{\sn fFlipH}{\sv 0}}{\sp{\sn fFlipV}{\sv 0}}{\sp{\sn fillColor}{\sv 12632256}}{\sp{\sn fFilled}{\sv 0}}}{\shprslt{\*\do\dobxcolumn\dobypara\dodhgt8192\dprect\dpx-120\dpy0\dpxsize8520\dpysize5832
\dpfillfgcr255\dpfillfgcg255\dpfillfgcb255\dpfillbgcr192\dpfillbgcg192\dpfillbgcb192\dpfillpat0\dplinew15\dplinecor0\dplinecog0\dplinecob0}}}}{\b CIS 480 DECIDABILITY TEMPLATE:
\par 1. \tab state the problem: }{(you may give the problem a name, }{\b also}{, if you like)}{\b \tab 
\par \tab }{problem: Does a given DFA accept a given string? Let's call this the acceptance problem for DFA's.
\par }{\b 
\par 2.\tab give a language corresponding to that problem:
\par       \tab }{corresponding language: A}{\sub DFA}{ = \{<B,w> | B is a DFA that accepts string w\}
\par }{\b 
\par 3.\tab give a TM that decides that language, 
\par \tab \tab with a first line giving the name and describing the input to the TM,
\par \tab \tab and numbered steps describing the actions of the TM (on a high level),
\par \tab \tab making sure to clearly indicate when the TM enters its accepting or rejecting states with  
\par }\pard \fi360\li1080\widctlpar\adjustright {\b ACCEPT and REJECT.
\par }\pard \fi-360\li360\widctlpar\adjustright {\b \tab }{Here is a TM that decides A}{\sub DFA}{:
\par \tab M = "On input <B,w>, where B is a DFA and w is a string,
\par \tab \tab 1. Simulate B on input w.
\par \tab \tab 2. If the simulation ends in an accept state, }{\b ACCEPT}{. If it ends in a 
\par \tab \tab     non-accepting state, }{\b REJECT}{."
\par }{\b 
\par 4.\tab give an appropriate concluding statement:
\par \tab }{M decides A}{\sub DFA}{, so A}{\sub DFA}{ is Turing-decidable, and so the problem "Does a given DFA
\par \tab accept a given string?" is indeed decidable.
\par \tab }{\b (or...) 
\par \tab }{M decides A}{\sub DFA}{, so A}{\sub DFA}{ is Turing-decidable, and so the acceptance problem for DFA's is indeed decidable.}{\b 
\par }\pard \widctlpar\adjustright {\b 
\par Note: }{For the following questions, you may assume that the following languages (from Ch. 4 of the class text) are known decidable:
\par \tab A}{\sub DFA}{, A}{\sub NFA}{, A}{\sub REX}{, E}{\sub DFA}{, EQ}{\sub DFA}{, A}{\sub CFG}{, E}{\sub CFG}{
\par 
\par So, TM's that decide these may be used in the solutions to the following problems. Be sure to clearly state which language's TM is being used in such cases, however.
\par 
\par }\pard \fi-360\li360\widctlpar\adjustright {2.\tab Consider the problem of determining whether a given DFA accepts both of two given strings. Show that this problem is decidable.
\par 
\par 3.   \tab Consider the problem of determining whether a given PDA accepts a given string. Show that this problem is decidable.
\par \tab 
\par }\pard \widctlpar\adjustright {\b Note the following required format (for this class) for showing that a problem is undecidable by use of a reduction:
\par }\pard\plain \s2\keepn\widctlpar\outlinelevel1\adjustright \cgrid {\b\fs20\lang1024 {\shp{\*\shpinst\shpleft-96\shptop24\shpright8856\shpbottom6024\shpfhdr0\shpbxcolumn\shpbypara\shpwr3\shpwrk0\shpfblwtxt0\shpz1\shplid1027
{\sp{\sn shapeType}{\sv 1}}{\sp{\sn fFlipH}{\sv 0}}{\sp{\sn fFlipV}{\sv 0}}{\sp{\sn fFilled}{\sv 0}}}{\shprslt{\*\do\dobxcolumn\dobypara\dodhgt8193\dprect\dpx-96\dpy24\dpxsize8952\dpysize6000
\dpfillfgcr255\dpfillfgcg255\dpfillfgcb255\dpfillbgcr255\dpfillbgcg255\dpfillbgcb255\dpfillpat0\dplinew15\dplinecor0\dplinecog0\dplinecob0}}}}{\b\fs20 CIS 480 REDUCTION TEMPLATE:
\par }\pard\plain \fi-360\li360\widctlpar\adjustright \fs20\cgrid {\b 1.\tab state the problem, giving it a name, also:
\par }\pard \widctlpar\adjustright {*   Consider problem }{\b X}{, the (yes/no) problem determining whether }{\b Y}{.}{\b 
\par }{\b\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 2.\tab make the following statement of your purpose:
\par }\pard \widctlpar\adjustright {        *   We use the undecidability of }{\b <known undecidable problem>}{ to prove the 
\par         undecidability of }{\b X}{ by reducing }{\b <known undecidable problem>}{ to }{\b X}{.}{\b 
\par }{\b\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 3.\tab explicitly state your assumption:
\par }\pard \widctlpar\adjustright {\b         }{*   ASSUME we have a TM R that decides }{\b X}{.
\par }\pard \fi-360\li360\widctlpar\adjustright {
\par {\pntext\pard\plain\b\fs20\cgrid \hich\af0\dbch\af0\loch\f0 4.\tab}}\pard \fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlbody\ilvl0\ls1\pnrnot0\pndec\pnstart4\pnindent360\pnhang{\pntxta .}}\ls1\adjustright {\b make the following 
statement, followed by the appropriate TM, stated using the same 
\par }\pard \li360\widctlpar\adjustright {\b standards as used in the CIS 480 DECIDABILITY TEMPLATE:
\par }\pard \widctlpar\adjustright {\b         }{*   Use R to construct S, a TM that decides }{\b <known undecidable problem>}{.
\par }{\b         }{*   S = "On input \'85
\par }{\b                 }{1. 
\par                 2. 
\par                 \'85
\par }{\fs24 
\par }\pard \fi-360\li360\widctlpar\adjustright {\b 5.\tab give an appropriate concluding statement:
\par }\pard \widctlpar\adjustright {        *   If R decides }{\b X}{, then S decides }{\b <known undecidable problem>}{. CONTRADICTION;
\par }{\b         }{*   Because }{\b <known undecidable problem>}{ is undecidable, we know that there can 
\par         be NO decider/algorithm for }{\b <known undecidable problem>}{; so, }{\b X}{ also must be 
\par         undecidable.}{\b 
\par 
\par Note:}{ For the following questions, you may assume that the following languages (from Ch. 5 of the class text, or in-class notes) correspond to known-undecidable problems:
\par \tab HALT}{\sub TM}{, E}{\sub TM}{, REGULAR}{\sub TM}{, ET}{\sub TM}{, ANYHALT}{\sub TM}{, ALLHALT}{\sub TM}{, SAMEHALT}{\sub TM}{
\par 
\par }\pard \fi-360\li360\widctlpar\adjustright {4.\tab Consider the problem: 
\par }\pard \widctlpar\adjustright {\b         AA}{\b\sub TM}{\b  = the problem of testing whether two given strings are both accepted by a given TM.
\par }{ 
\par }\pard \fi-360\li360\widctlpar\adjustright {\tab Show that this problem is undecidable.
\par 
\par 5.\tab Consider the problem: 
\par }\pard \widctlpar\adjustright {\b         EQ}{\b\sub TM }{\b = the problem of testing whether the languages of two TM's are the same}{.
\par }\pard \fi-360\li360\widctlpar\adjustright {
\par \tab Show that this problem is undecidable. 
\par 
\par }\pard \li360\widctlpar\adjustright {(Hint: }{\b one}{ way to do so involves E}{\sub TM}{; also, in your reduction, make use of a TM M}{\sub 1}{ }{\b known}{ to reject all inputs (whose corresponding language is }{\b known}{ to be empty).)
\par }\pard \fi-360\li360\widctlpar\adjustright {
\par }\pard \widctlpar\adjustright {\b 
\par }{
\par }}