NetID:

Modeling Computation

$($a$)(3$ points$)$ Design a Context Free Grammar $G$ such that

$L(G)=\{\begin{array}{c}{b}^n{a}^m{b}^n|m0\end{array}$ and $\{$:$n0\}$

$($b$)$ Given the regular expression

$r=c(c|d)(a|b)b(c|d)c$

i$.(3$ points$)$ List all the strings represented by $r.$

ii$.(3$ points$)$ Draw a NFA$-lon$ that accepts the language represented by $r.$Name:

NetID:

Number Theory

$($a$)(3$ points$)$ Definition: $a-=b(modm)$ if and only if $m|(a-b)$

Prove that $a-=b(modm)$ if and only if amodm$=$bmodm.

$($b$)(2$ points$)$ Do the following operation and express the answer as a base $3$ expansion.

$(2112{)}_3+(12021{)}_3$

$($c$)(2$ points$)$ Find $gcd(1000,625)$ and lcm$(1000,625).$Induction

$($a$)(3$ points$)$ Prove by induction that

${\displaystyle \underset{i=1}{\overset{n}{}}}i(i+1)(i-1)=\frac{n(n+1)(n+2)(n-1)}{4},$AAn$1$

$($b$)(3$ points$)$ Prove by strong induction that AAn$18,$EEa,bin$\{0,1,2,$dots$\},n=4a+7b$

Hint: Start by proving that it is true for nin$\{18,19,20,21\}$