{\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;}{\*\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\listtemplateid-1388250038\listsimple{\listlevel\levelnfc4
\leveljc0\levelfollow0\levelstartat4\levelspace0\levelindent0{\leveltext\'03(\'00);}{\levelnumbers\'02;}\fbias0 \fi-390\li780\jclisttab\tx780 }{\listname ;}\listid724841894}}{\*\listoverridetable{\listoverride\listid724841894\listoverridecount0\ls1}}
{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Academic Computing}{\creatim\yr2000\mo2\dy11\hr9\min29}{\revtim\yr2000\mo2\dy11\hr9\min29}{\printim\yr1998\mo9\dy16\hr10\min46}{\version2}{\edmins0}{\nofpages2}{\nofwords230}
{\nofchars1312}{\*\company CNRS - HSU}{\nofcharsws1611}{\vern113}}\widowctrl\ftnbj\aenddoc\lytprtmet\formshade\viewkind1\viewscale75\pgbrdrhead\pgbrdrfoot \fet0\sectd \linex0\endnhere\sectdefaultcl {\header \pard\plain \s15\widctlpar
\tqc\tx4320\tqr\tx8640\adjustright \fs20\cgrid {\fs18 CIS 480 - Homework #2\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\adjustright \fs20\cgrid {\b CIS 480 - Computer Theory - Spring 2000
\par HOMEWORK #2
\par DUE: February 18, 2000, 12:00 noon}{\b\fs24 
\par }\pard \widctlpar\adjustright {\fs24 
\par }{Please send the answers to the following to me by e-mail (and }{\b not}{ using attachments, please!). Send them to }{\b st10@axe.humboldt.edu}{, and make sure that the Subject: is }{\b 480 hw 2}{
. Label each answer with the problem number and part letter.
\par 
\par Note: since you will need to type this in ASCII, please avoid use of the superscript + (as opposed to + for union); remember, for example, that 1}{\super + }{is equivalent to 11*.
\par 
\par In this homework, assume that the alphabet }{{\field{\*\fldinst SYMBOL 229 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ is \{0, 1\}.
\par 
\par 1.   (25 pts)  For each of the following, give an equivalent regular expression:
\par         (a)   \{w | w begins with a 1 and ends with a 0\}
\par 
\par         (b)   \{w | w contains the substring 0101\}
\par 
\par         (c)   \{w | w has length 3\}
\par 
\par {\pntext\pard\plain\fs20\cgrid \hich\af0\dbch\af0\loch\f0 (d)\tab}}\pard \fi-390\li780\widctlpar\jclisttab\tx780{\*\pn \pnlvlbody\ilvl0\ls1\pnrnot0\pnlcltr\pnstart4\pnindent780\pnhang{\pntxtb (}{\pntxta )}}\ls1\adjustright {\{w | w begins with 111 or 00\}

\par }\pard \widctlpar\adjustright {
\par }\pard \li390\widctlpar\adjustright {(e)   \{w | w contains at least two 0\rquote s\}
\par }\pard \widctlpar\adjustright {
\par 2.   (20 pts) For each of the following languages, give two strings that }{\b are}{ members, and two strings that are }{\b not}{ members (or, a total of four strings for each language below).
\par         (a)   0(10)*1
\par 
\par         (b)   (000)*
\par 
\par         (c)   (0+1)*0(0+1)*1(0+1)*0(0+1)*
\par 
\par         (d)   010 + 101
\par 
\par 3.   (20 pts) Consider the following NFA. Give an equivalent regular expression.
\par 
\par }{\fs24 {\pict{\*\picprop\shplid1025{\sp{\sn shapeType}{\sv 75}}{\sp{\sn fFlipH}{\sv 0}}{\sp{\sn fFlipV}{\sv 0}}{\sp{\sn fillColor}{\sv 268435473}}{\sp{\sn fFilled}{\sv 0}}{\sp{\sn fLine}{\sv 0}}}
\picscalex100\picscaley100\piccropl0\piccropr0\piccropt0\piccropb0\picw10160\pich2693\picwgoal5760\pichgoal1527\wmetafile8\bliptag1240301067\blipupi-352{\*\blipuid 49ed7e0b63e8c9d2d09722d59d19fe08}
0100090000030e05000006002a00000000001100000026060f001800ffffffff0000100028f6ffff3e00000028ffffffa10200000900000026060f000800ffff
ffff020000001000000026060f001600ffffffff04000e00544e5050070038513d50610575000a00000026060f000a00544e505000000200f003090000002606
0f000800ffffffff030000000f00000026060f001400544e505004000c00010000000100000000000000050000000b023e0028f6050000000c02630200090900
0000fa02050000000000ffffff002200040000002d01000007000000fc020100000000000000040000002d01010009000000fa02060008000000000000022200
040000002d0102000400000004010d000700000018045f01b3f77d00c2f615000000fb02b1ff0000000000009001000000000000001254696d6573204e657720
526f6d616e003872040000002d010300040000002e011800050000000a0200000000050000000902000000020500000014020000000004000000020101000a00
0000320a03010df7020000007131280028000400000002010200070000001804640136fa820045f90700000018046e0172fc8c0081fb0700000018046e010dff
8c001cfe15000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e001500040000002d01040004000000f00103000400
00002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320afe0090f902000000713228002800
040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000002d01030004000000f001
0400040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320a0801cdfb020000007133
28002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e001500040000002d0104000400
0000f0010300040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000a000000320a080180fe0200
000071342800280004000000020102002a0000002503130013f75a010af7850105f7980105f7a60105f7ba0105f7cd0105f7e0010ef7f3012bf7fd0148f70202
6ef706028bf71002a8f71002cef71002e2f7f301e2f7cd01e6f7a601e6f79c01dbf77f01040000002d01000007000000fc020000000000020000040000002d01
0300050000000902000000020c000000240304000af88f01e1f78e01c3f7aa01bbf72a0105000000090200000002040000002d010000040000002d0101000400
0000f001020004000000f001030010000000fb021400090000000000bc02000000000102022253797374656d006e040000002d01020004000000f00104000300
00001e000700000016040640f2f801c0b2f709000000fa02060008000000000000022200040000002d010300050000001402ce00b0f7050000001302ce00ecf8
040000002d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d01030005000000090200000002
0c00000024030400cbf8f400daf8ce00cbf8a80045f9ce0005000000090200000002040000002d010000040000002d01010004000000f0010300030000001e00
070000001604064032fb01c03efa09000000fa02060008000000000000022200040000002d010300050000001402e6003cfa050000001302e6002cfb04000000
2d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000000902000000020c000000
240304000bfb0c011afbe6000bfbc00085fbe60005000000090200000002040000002d010000040000002d01010004000000f0010300030000001e0007000000
16040640bffd01c07afc09000000fa02060008000000000000022200040000002d010300050000001402f50078fc050000001302f500b9fd040000002d010000
040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000000902000000020c00000024030400
98fd1b01a7fdf50098fdcf0012fef50015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000002d01
0400040000002e011800050000000a020000000005000000090200000002050000001402f500b9fd04000000020101000d000000320a6b0243f704000000302c
20312800140014002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e00150004000000
2d01050004000000f0010400040000002e011800050000000a020000000005000000090200000002050000001402ffff69d4040000000201010009000000320a
a30033f80100000031002800040000000201020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e0038720400
00002d01040004000000f0010500040000002e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000c000000
320ab60086fa03000000302c2000280014001400040000000201020010000000fb02b0ff0000000000009001000000020000001253796d626f6c000004000000
2d01050004000000f001040005000000090200000002050000001402ffff69d4040000000201010009000000320ab600d6fa0100000031002800040000000201
020015000000fb02b1ff0000000000009001000000000000001254696d6573204e657720526f6d616e003872040000002d01040004000000f001050004000000
2e011800050000000a020000000005000000090200000002050000001402ffff69d404000000020101000c000000320ab600f2fc03000000302c310028001400
2800040000000201020005000000090200000002040000002d010000040000002d01010004000000f0010300040000002d01020004000000f001040003000000
1e0007000000160406406ef601c028f609000000fa02060008000000000000022200040000002d010300050000001402d80026f6050000001302d80068f60400
00002d010000040000002d01010004000000f0010300040000002701ffff07000000fc020000000000020000040000002d010300050000000902000000020c00
00002403040048f6fe0057f6d80048f6b200c2f6d80009000000fa02060008000000000000022200040000002d010400040000002d0101000700000018048601
28ff6f00effd0f00000026060f001400544e505004000c000000000000000000000000000900000026060f000800ffffffff01000000040000002d010000040000002d01010004000000f001040004000000f0010300030000000000}}{
\par 
\par 4.   (25 pts) Give an FA (NFA or DFA, your choice) using the formal FA notation for the following RE; since you are restricted to ASCII, \ldblquote write out\rdblquote  the Greek letters as needed, and write subscripts simply after their letter:
\par \tab }{{\field{\*\fldinst SYMBOL 229 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ = sigma
\par \tab }{{\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{ = delta
\par \tab q}{\sub 0}{ = q0
\par 
\par \tab (0+1)*010*
\par 
\par 
\par (continued)
\par 5.   (10 pts) Consider the following NFA. Give an equivalent regular expression.
\par }\pard \li1440\widctlpar\adjustright {{\pict{\*\picprop\shplid1026{\sp{\sn shapeType}{\sv 75}}{\sp{\sn fFlipH}{\sv 0}}{\sp{\sn fFlipV}{\sv 0}}{\sp{\sn fillColor}{\sv 268435473}}{\sp{\sn fFilled}{\sv 0}}{\sp{\sn fLine}{\sv 0}}}
\picscalex100\picscaley100\piccropl0\piccropr0\piccropt0\piccropb0\picw9193\pich9529\picwgoal5212\pichgoal5402\wmetafile8\bliptag1033330602\blipupi-61{\*\blipuid 3d975faa6843810a8b39d9a6ceb896bc}
0100090000031c06000006003000000000001100000026060f001800ffffffff00001000d601000046f8fffffb090000b70000000900000026060f000800ffff
ffff020000001000000026060f001600ffffffff04000e00544e5050070038513d50610575000a00000026060f000a00544e505000000200f003090000002606
0f000800ffffffff030000000f00000026060f001400544e505004000c00010000000100000000000000050000000b0246f8d601050000000c02710825080900
0000fa02050000000000ffffff002200040000002d01000007000000fc020100000000000000040000002d01010009000000fa02060008000000000000022200
040000002d0102000400000004010d0007000000180401faa108e0f8800707000000180401fa8104e0f8600307000000180451fe510430fd3003070000001804
21fed10800fdb007040000002d010000040000002d01010004000000f0010200030000001e0007000000160406402e0701c0800409000000fa02060008000000
000000022200040000002d01020005000000140270f97e0405000000130270f92807040000002d010000040000002d01010004000000f0010200040000002701
ffff07000000fc020000000000020000040000002d010200050000000902000000020c00000024030400060796f9150770f906074af9800770f9050000000902
00000002040000002d010000040000002d01010004000000f0010200030000001e00070000001604aefc064000fa01c009000000fa0206000800000000000002
2200040000002d010200050000001402fef94008050000001302a8fc4008040000002d010000040000002d01010004000000f0010200040000002701ffff0700
0000fc020000000000020000040000002d010200050000000902000000020c000000240304001a0886fc400895fc660886fc400800fd09000000fa0206000800
0000000000022200040000002d010300040000002d01010007000000180451fe0109d0fc8007040000002d010000040000002d01010004000000f00103000400
0000f0010200030000001e0007000000160406400c0301c0e00109000000fa02060008000000000000022200040000002d01020005000000140270f9de010500
0000130270f90603040000002d010000040000002d01010004000000f0010200040000002701ffff07000000fc020000000000020000040000002d0102000500
00000902000000020c00000024030400e60296f9f50270f9e6024af9600370f905000000090200000002040000002d010000040000002d01010004000000f001
0200030000001e00070000001604ddfc064000fa01c009000000fa02060008000000000000022200040000002d010200050000001402fef9f003050000001302
d7fcf003040000002d010000040000002d01010004000000f0010200040000002701ffff07000000fc020000000000020000040000002d010200050000000902
000000020c00000024030400ca03b6fcf003c5fc1604b6fcf00330fd09000000fa02060008000000000000022200040000002d010300040000002d0101002e00
0000250315003003c0fddd02d4fd9102d4fd6b02d4fd5f02eefd390207fe2c0239fe1f0253fe1f0285fe1f02b8fe2c02eafe45021dff5f0236ffc40243fff602
4fff42034fff680343ff810329ff8e03f7fe9203e6fe9d03b7fe040000002d010000040000002d010200050000000902000000020c00000024030400bb03dffe
9a03c7fe7103ccfeb4035ffe05000000090200000002040000002d010000040000002d01010004000000f001030004000000f0010200030000001e0007000000
1604f8fab807d0f9700509000000fa02060008000000000000022200040000002d010200050000001402d0f9b007050000001302f0fa7005040000002d010000
040000002d01010004000000f0010200040000002701ffff040000002d010000040000002d010100030000001e0007000000160415fd0640f0fa01c009000000
fa02060008000000000000022200040000002d010200050000001402f0fa70050500000013020dfd7604040000002d010000040000002d01010004000000f001
0200040000002701ffff07000000fc020000000000020000040000002d010200050000000902000000020c000000240304006104e1fc7d04fffca60401fd5004
60fd05000000090200000002040000002d010000040000002d01010004000000f0010200030000001e0007000000160498fdc806e0fb500409000000fa020600
08000000000000022200040000002d01020005000000140290fd5004050000001302e0fbc006040000002d010000040000002d01010004000000f00102000400
00002701ffff040000002d010000040000002d010100030000001e0007000000160418fcb8074bfa900609000000fa0206000800000000000002220004000000
2d01020005000000140210fc90060500000013024bfab007040000002d010000040000002d01010004000000f0010200040000002701ffff07000000fc020000
000000020000040000002d010200050000000902000000020c00000024030400bf077bfaa7075afa7f0753fae00700fa09000000fa0206000800000000000002
2200040000002d010300040000002d0101003000000025031600e90856fe05096bfe080979fe220979fe3b09abfe3b09defe3b0910ff3b0943ff15095cffe308
75ffc90875ff97088eff7d088eff4b088eff180868ffff0736ffe60710ffe607eafee607b8fee6079efef20779fe0c085ffe040000002d010000040000002d01
0200050000000902000000020c0000002403040019094afef60860feeb0887fea00820fe15000000fb0240ff0000000000009001000000000000001254696d65
73204e657720526f6d616e001100040000002d010400040000002e011800050000000a0200000000050000000902000000020500000014024bfab00704000000
0201010009000000320a10f970050100000030006000040000000201020015000000fb0240ff0000000000009001000000000000001254696d6573204e657720
526f6d616e001900040000002d01050004000000f0010400040000002e011800050000000a020000000005000000090200000002050000001402ffff69d40400
00000201010009000000320a80fb30030100000031006000040000000201020015000000fb0240ff0000000000009001000000000000001254696d6573204e65
7720526f6d616e001100040000002d01040004000000f0010500040000002e011800050000000a020000000005000000090200000002050000001402ffff69d4
040000000201010009000000320a300010020100000030006000040000000201020015000000fb0240ff0000000000009001000000000000001254696d657320
4e657720526f6d616e001900040000002d01050004000000f0010400040000002e011800050000000a020000000005000000090200000002050000001402ffff
69d4040000000201010009000000320a90fa40050100000031006000040000000201020015000000fb0240ff0000000000009001000000000000001254696d65
73204e657720526f6d616e001100040000002d01040004000000f0010500040000002e011800050000000a020000000005000000090200000002050000001402
ffff69d4040000000201010009000000320a00fd00060100000030006000040000000201020015000000fb0240ff000000000000900100000000000000125469
6d6573204e657720526f6d616e001900040000002d01050004000000f0010400040000002e011800050000000a02000000000500000009020000000205000000
1402ffff69d4040000000201010009000000320a80fba0080100000031006000040000000201020015000000fb0240ff00000000000090010000000000000012
54696d6573204e657720526f6d616e001100040000002d01040004000000f0010500040000002e011800050000000a0200000000050000000902000000020500
00001402ffff69d404000000020101000d000000320a6000a00804000000302c2031600030003000600004000000020102000f00000026060f001400544e5050
04000c000000000000000000000000000900000026060f000800ffffffff01000000040000002d010000040000002d01010004000000f001030004000000f001020010000000fb021400090000000000bc02000000000102022253797374656d006e040000002d01020004000000f0010400030000000000}}{\fs24 

\par }\pard \widctlpar\adjustright {\b\fs24 
\par }}