{\rtf1\ansi \deff4\deflang1033{\fonttbl{\f4\froman\fcharset0\fprq2 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 
\f4\fs20 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext16 footer;}{\*\cs17 \additive\sbasedon10 
page number;}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Sharon M. Tuttle}{\creatim\yr2000\mo1\dy15\hr2\min58}{\revtim\yr2000\mo1\dy15\hr19}{\version11}{\edmins216}{\nofpages1}{\nofwords195}{\nofchars1113}
{\*\company CNRS - HSU}{\vern57431}}\widowctrl\ftnbj\aenddoc\formshade \fet0\sectd \linex0\endnhere {\header \pard\plain \s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 {\fs18 CIS 480 - Homework #1\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 \qc\widctlpar \f4\fs20 {\b CIS 480 - Computer Theory - Spring 2000
\par HOMEWORK #1
\par DUE: Wednesday, February 9th, Beginning of Class}{\b\fs24 
\par }\pard \qc\widctlpar {\b\fs24 
\par }\pard \widctlpar {\fs24 Turn in this assignment on-paper; hand-drawings will be fine!}{\b\fs24 
\par 
\par }\pard \widctlpar {\b\fs24 1. }{\fs24 Draw the }{\b\fs24 state diagram}{\fs24  of a DFA that }{\b\fs24 accepts}{\fs24  all strings from the alphabet \{0,1\} that begin with a 1 and end with a 1.}{\b\fs24 
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 2. }{\fs24 Draw the }{\b\fs24 state diagram}{\fs24  of a DFA that }{\b\fs24 accepts}{\fs24  all strings from the alphabet 
\par }\pard \widctlpar {\fs24 \{0, 1\} that contain }{\b\fs24 three consecutive 0's}{\fs24  anywhere within them.}{\b\fs24 
\par 
\par }\pard \widctlpar {\b\fs24 3. }{\fs24 Draw the }{\b\fs24 state diagram}{\fs24  of a DFA that }{\b\fs24 accepts}{\fs24  all strings from the alphabet \{0,1\} that contain at least }{\b\fs24 three}{\fs24  0
's within them (they need not be consecutive, note!)}{\b\fs24 
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 4. }{\fs24 Draw the }{\b\fs24 state diagram}{\fs24  of a DFA that }{\b\fs24 accepts}{\fs24  only strings from the alphabet 
\par \{0, 1\} in which there are }{\b\fs24 NOT}{\fs24  at least }{\b\fs24 three}{\fs24  0's within them (only strings with zero, one, or two 0's are in this language).
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 5. }{\fs24 Choose one of your answers to }{\b\fs24 1-4}{\fs24 . Indicate your choice, and express your DFA for that problem in the formal 5-tuple notation for a DFA.}{\b\fs24 
\par }\pard \widctlpar {\fs24 
\par }\pard \widctlpar {\b\fs24 6. }{\fs24 Draw the "tree of possibilities" (as demonstrated in lecture, or in Figure 1.16 on p. 50) for the string }{\b\fs24 01101}{\fs24  for the following NFA:
\par }\pard \widctlpar {\fs24 
\par }\pard \li720\widctlpar {\fs24 {\pict\wmetafile8\picw10160\pich2694\picwgoal5760\pichgoal1527 
0100090000030e05000006002a00000000001100000026060f001800ffffffff0000100028f6ffff3e00000028ffffffa10200000900000026060f000800ffffffff020000001000000026060f001600ffffffff04000e00544e5050070038513d50610575000a00000026060f000a00544e505000000200f0030900000026
060f000800ffffffff030000000f00000026060f001400544e505004000c00010000000100000000000000050000000b023e0028f6050000000c026302000909000000fa02050000000000ffffff002200040000002d01000007000000fc020100000000000000040000002d01010009000000fa0206000800000000000002
2200040000002d0102000400000004010d000700000018045f01b3f77d00c2f615000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000002d010300040000002e011800050000000a0200000000050000000902000000020500000014020000000004000000020101
000a000000320a03010df7020000007131280028000400000002010200070000001804640136fa820045f90700000018046e0172fc8c0081fb0700000018046e010dff8c001cfe15000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e001500040000002d01040004000000f001
0300040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320afe0090f902000000713228002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000002d01030004
000000f0010400040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320a0801cdfb02000000713328002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e00150004000000
2d01040004000000f0010300040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320a080180fe0200000071342800280004000000020102002a0000002503130013f75a010af7850105f7980105f7a60105f7ba0105f7cd0105f7e0010ef7f3012b
f7fd0148f702026ef706028bf71002a8f71002cef71002e2f7f301e2f7cd01e6f7a601e6f79c01dbf77f01040000002d01000007000000fc020000000000020000040000002d010300050000000902000000020c000000240304000af88f01e1f78e01c3f7aa01bbf72a0105000000090200000002040000002d0100000400
00002d01010004000000f001020004000000f001030010000000fb021400090000000000bc02000000000102022253797374656d006e040000002d01020004000000f0010400030000001e000700000016040640f2f801c0b2f709000000fa02060008000000000000022200040000002d010300050000001402ce00b0f705
0000001302ce00ecf8040000002d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000000902000000020c00000024030400cbf8f400daf8ce00cbf8a80045f9ce0005000000090200000002040000002d010000040000002d01010004000000
f0010300030000001e00070000001604064032fb01c03efa09000000fa02060008000000000000022200040000002d010300050000001402e6003cfa050000001302e6002cfb040000002d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000
000902000000020c000000240304000bfb0c011afbe6000bfbc00085fbe60005000000090200000002040000002d010000040000002d01010004000000f0010300030000001e000700000016040640bffd01c07afc09000000fa02060008000000000000022200040000002d010300050000001402f50078fc050000001302
f500b9fd040000002d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000000902000000020c0000002403040098fd1b01a7fdf50098fdcf0012fef50015000000fb02b1ff0000000000009001000000000000001254696d6573204e65772052
6f6d616e003872040000002d010400040000002e011800050000000a020000000005000000090200000002050000001402f500b9fd04000000020101000d000000320a6b0243f704000000302c20312800140014002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e65
7720526f6d616e001500040000002d01050004000000f0010400040000002e011800050000000a020000000005000000090200000002050000001402ffff69d4040000000201010009000000320aa30033f80100000031002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573
204e657720526f6d616e003872040000002d01040004000000f0010500040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000c000000320ab60086fa03000000302c2000280014001400040000000201020010000000fb02b0ff000000000000900100000002
0000001253796d626f6c0000040000002d01050004000000f001040005000000090200000002050000001402ffff69d4040000000201010009000000320ab600d6fa0100000031002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000
002d01040004000000f0010500040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000c000000320ab600f2fc03000000302c3100280014002800040000000201020005000000090200000002040000002d010000040000002d01010004000000f00103000400
00002d01020004000000f0010400030000001e0007000000160406406ef601c028f609000000fa02060008000000000000022200040000002d010300050000001402d80026f6050000001302d80068f6040000002d010000040000002d01010004000000f0010300040000002701ffff07000000fc02000000000002000004
0000002d010300050000000902000000020c0000002403040048f6fe0057f6d80048f6b200c2f6d80009000000fa02060008000000000000022200040000002d010400040000002d010100070000001804860128ff6f00effd0f00000026060f001400544e505004000c000000000000000000000000000900000026060f00
0800ffffffff01000000040000002d010000040000002d01010004000000f001040004000000f0010300030000000000}}{\fs24 
\par }\pard \widctlpar {\b\fs24 7.}{\fs24  Is }{\b\fs24 01101}{\fs24  accepted by the NFA depicted in problem 6? How can you tell, from the tree of possibilities?
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 8. }{\fs24 Draw an NFA (that is NOT also a DFA) that accepts all strings from the alphabet \{0, 1\} containing a 0 in either the third or second position from the end.}{\b\fs24 
\par }}