$($Graded for correctness$){|}^2$ Functions over languages $(15$ points$)$:

For languages $L_1,L_2$ over the alphabet ${}_1=\{0,1\},$ we have the associated sets of strings

SUBSTRING$(L_1)=\{\begin{array}{cc}\text{w}\text{i}\text{n}& {}_1^{**}|\end{array}$ there exist $a,$bin${}_1^{**}$ such that $\{$:$awbin{L}_1\}$

and

$L_1$@$L_2=\{win{}_1^{**}|w=uv$ for some strings $uin{L}_1$ and $vin{L}_2\}$

$($a$)$ Specify an example language A over ${}_1$ such that $A\frac{O}{?}$ and yet Substring$(A)=\frac{O}{?},$ or

explain why there is no such example. A complete solution will include either $(1)$ a precise

and clear description of your example language A and a precise and clear description of the

result of computing Substring $(A)$ using relevant definitions to justify this description and

to justify the set equality with $\frac{O}{?},$ or $(2)$ a sufficiently general and correct argument why

there is no such example, referring back to the relevant definitions.

$($b$)$ Specify example languages $B,C$ over ${}_1$ such that $B{}_1^{**}$ and $C{}_1^{**}$ and yet $B$@

$C={}_1^{**},$ or explain why there are no such examples. A complete solution will include

either $(1)$ a precise and clear description of your example languages $B,C$ and a precise and

clear description of the result of computing $B$@$C$ using relevant definitions to justify this

description and to justify the set equality with ${}_1^{**},$ or $(2)$ a sufficiently general and correct

argument why there is no such example, referring back to the relevant definitions.

$($c$)$ Specify example finite languages $L_1,L_2$ over ${}_1$ such that $L_1$@$L_2{L}_1$ but $|L_1$@$L_2|=|L_1|,$ or

explain why there are no such examples. A complete solution will include either $(1)$ a precise

and clear description of your example languages $L_1,L_2$ and a precise and clear description

of the result of computing $L_1$@$L_2$ using relevant definitions to justify this description and

to justify the cardinality claims and set $($in$)$equality claims, or $(2)$ a sufficiently general and

correct argument why there is no such example, referring back to the relevant definitions.