$1.$ Calculate denotational semantics for the following nondeterministic programs.a$.$ LetS $=$ ifx$>$yx$==$x$-10$x$>$yy$=$y$+10$x$+$y$=4$x$=$y$/$x $0$x$+$y$=4$x:$=$x$/$y fi$,$ and let o $=\{$x $=3,$ y $=1\}.$ Calculate M$($S$,$ o$)$ and show your work.b$.$ LetW $=$ dox$>$ y x$=$x$-10$x$>$yy$=$y$+10$x$+$y$=4$x$=$y$/$x $0$x$+$y$=4$ x:$=$x$/$y od$,$ and let o $=\{$x $=3,$ y $=1\}.$ Calculate M $($W$,$o$)$ and show your work.

$2.$ Let b be an array of size n $1,$ and VO i $$ n$.$ bli$|=0$ v b$[$il $=1.$ Decide which number $(0$ or $1)$ is the majority in b without counting their quantities.Write a program named MAJORITY in our language that can solve the above problem and bind the majority among $0$ and $1$ to variable major. You can assume that b is written in the memory state; and to simplify thequestion, we artificially define b $[$n$]=100,$ so you don't need to worry about a possible runtime error when thearray index reaches n$.$ Your program doesn't have to be deterministic. Be careful of the grammar in our programming language.Here are some hints:$1)$ We can use the following linear$-$search$-$like algorithm: scan the array b to pair up each $0$ with a $1.$ Once we have some $1\text{'}$s left over, then $1$ is the majority; once we have some O$\text{'}$s left over, then O is the majority; if we can pair up all numbers, then either of them can be the majority$\mathrm{.}2)$ A student Jason wrote a partial solution that can be useful to solve the above problem:$/=$ dob$|$kol $=1$ ko:$=$ ko$+10$bk$11=0$k$1=$k$1+1$odConsider ko and ky as pointers for number $0$ and $1$ respectively. What program J does is to find the nextko and ky such that b$|$kol $=0$ and b$|$kil $=1.$ You can use f inside of your program.

$3.$ True or false. Justify your answer briefly.a$.$ If M$($S$,$o$)$ contains exactly one state, then S must be a deterministic statement.b$.$ Ifo $=($p$\}$S $\{9\},$ then o Ep$.$C$.$ If o #tot $($p$\}$S $\{9\},$ then o # p$.$d$.$ Ifo F $($p$\}$S $\{$q$),$ then M$($S$,$o$)$ Fq$.$e$.$ Ifo # $($p$\}$S$\{$a$),$ then o #tot $\{$p$\}$ S $\{$q$\}.$

$4.$ Let predicate function P$($k$,$ s$)=$ s$\text{'}$ k $($s $+1)?.$ For each of the following triples, decide whether it is validunder total correctness, justify your answer briefly.a$.\{$P$($k$,$s $+1)\}$s $==5+1\{$P$($k$,$s$)\}$b$.\{$P$($k$,$ s$)\}$s $==$ s $+1\{$P$($k$,$s $+1)\}$c$.\{$P$($k$,$ s$)^$s $<mtext></mtext><mn>0</mn><mi>\}</mi>$s:$=$ s $+1$;k:$=$ k$+1\{$P$($k$,$s$)\}$d$.[$P$($k$,$s$)$ Ms $=$ So$\}$s $==$ s$+11$P$($k$,$ so$)\}$e$.\{$P$($k $+1,5+1)\}$s :$=$s $+1$;k:$=$ k$+1\{$P$($k$,$s$)\}.$

$5.$ Answer the following questions and justify your answer briefly.a$.$ Leto F$($x # $0\}$ while x # $0$ dox:$=$ x $-2$ od$\{$x what are the possible values of o$($x$)?$b$.$ Leto Ftot $\{$x # $0\}$ while x # $0$ do x :$=$ x $-2$ od $\{$x what are the possible values of o $($x$)?$