{\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\min19}{\revtim\yr2000\mo4\dy5\hr15\min19}
{\printim\yr1999\mo3\dy10\hr11\min37}{\version2}{\edmins0}{\nofpages1}{\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 - Decidability Template\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 - Decidability Template - Spring 2000

\par }\pard\plain \widctlpar\adjustright \fs20\cgrid {\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 
\par 
\par }{\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 }}