=========================preview======================
(COMP251)07-midterm-sol.pdf
Back to COMP251 Login to download
======================================================
Problem1 (a)a.[1,2,3,5]. (b)a.4. (c)a.13. (d)a.(2*2)*[(2*2)*(2*2)].64.
Problem2
(a)foo1.fn:int-.int (b)foo2.fn:'a*'a-.'alist (c)foo3.fn:(int*int-.'a)-.int-.'a (d)foo4.fn:bool-.my_color

Problem3
funMax[x].x |Max(x::xs).ifx.MaxxsthenxelseMaxxs.

Problem4
funInsert(x,[]).[x] |Insert(x,y::ys).ifx.ytheny::yselseifx.ytheny::Insert(x,ys)elsex::y::ys.

Problem5 (a)Therearetwoparsetreesforaabbb:
.S.-.a.S.b-.aa.S.bbb-.aabbb. .S.-.a.S.bb-.aa.S.bbb-.aabbb.

(b)ab,abb,aabb,aabbb,aabbbb,aaabbb,aaabbbb,aaabbbbb,aaabbbbbb (c)a nbmsuchthatn.m.2n.
Problem6
ca,caa,cba,da,daa,dba,a,aa,aaa,ba,baa,cca,dda

Problem7
(0|([1-9][0-9]*))."."[0-9]+

Problem8
.S.::..S1.|.empty. .S1.::..T.|.T..S1. .T.::.(.S1.)|()

Problem9
funlist_insert([],[]).[]
|list_insert(x::xs,y::ys).(x::y)::list_insert(xs,ys). funsingle_list[].[]
|single_list(x::xs).[x]::(single_listxs). funPerm[].[]
|Perm[x].single_listx
|Perm(x::xs).list_insert(x,Permxs).

Problem10
.S.::..E..-..S.|.E. .E.::..T.-..E.|.T. .T.::..T./\.U.|.T.\/.U.|.U. .U.::.-.U.|.V.
1
.V.::.x|y|(.S.)
-.
/\
-v

//\
()xy
/

v
/\
xy

or
-.
/\
-v
/|\/\
(v)xy
/\
xy

.S.
|
.E.
/|\
.T.-..E.
||
.U..T.
/\/|\

-.U..T.v.U.
|||
.V..U..V.
/|\||
(.S.).V.y
||
.E.x

|
.T.
/|\
.T.v.U.
||
.U..V.
||

.V.y
|
x


10.3Proof:Supposebothe1ande2canbegeneratedby.S.,weneedtoshowthate1-.e2
2


canalsobegeneratedby.S..Weprovebyinductiononthenumberof\$"operatorsin e1.Forthebasecase,supposee1hasno\$"operators.Thene1canbegeneratedby.E., thuse1$e2canbegeneratedby.S.usingthe.rstproductionrule.Inductively,suppose thatife1containsk\$"operators,thene1$e2canbegeneratedby.S..Weneedto showthatife1containsk+1\$"operators,thene1$e2canalsobegeneratedby.S.. Supposee1ise3$e4wheree3hasno\$"operatorinit.Thene4hask\$"operatorsin it.Sincee1canbegeneratedby.S.,thismeansthate3mustbegeneratedby.E.ande4 generatedby.S..Sincethenumberof\$"operatorsine4isk,byinductiveassumption, e4$e2canbegeneratedby.S.,thuse1$e2,whichise3$e4$e2,canbegeneratedby .S.usingthe.rstproductionrule.Thisprovestheinductivestep,thusconcludesthe proof.
3