CS403/SE307/CS355 - Theory of Computation

NUIMCrest CS403/SE307/CS355 - Theory of Computation
Selected sample solutions to Test 1 (A & B)
Tuesday 09 November 2004, 10:00, Lab 4

T Naughton, CS NUIM

QA1 111

QA2
./images/cs3552004test01solutionA02.png

QA3 L(M_a) = { w : w $in$ {0,1}*, w begins with a 1}

QA4 1(0 $union$ 1)*

QA5
./images/cs3552004test01solutionA05.png

QA6 (1*01*01*)*11

QA7
./images/cs3552004test01solutionA07.png

QA8 e $union$ 0 $union$ 1 $union$ (01 $union$ 10)(0 $union$ 1)*

QA9 (e $union$ 1 $union$ 11)(01 $union$ 011 $union$ 0)*

QA10
./images/cs3552004Machine4_8bsolution.png

QA11 (L₁*) $concatenate$ L₂ = {e, 0, b, 10, aa, b0, bb, aa0, aab, b10, ...}

QB1 010

QB3 L(M_a) = { w : w $in$ {a,b}*, w ends with an a}

QB4 (a $union$ b)*a

QB6 1*01*0(0 $union$ 1)*11

QB8 e $union$ 0 $union$ 1 $union$ (00 $union$ 11)(0 $union$ 1)*

QB9 0(00)* $union$ (0 $union$ 1)*1(00)*

QB11 (L₁*) $concatenate$ L₂ = {e, 1, a, 00, a1, aa, ab, a00, aa1, aaa, ...}