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).$