Functions over languages $(15$ points$)$:

For languages L$1,$ L$2$ over the alphabet $\backslash$Sigma $1=\{0,1\},$ we have the associated sets of strings

SU BST RIN G$($L$1)=\{$w in $\backslash$Sigma $$

$1|$ there exist a$,$ b in $\backslash$Sigma $$

$1$ such that awb in L$1\}$

and

L$1$ L$2=\{$w in $\backslash$Sigma $$

$1|$ w $=$ uv for some strings u in L$1$ and v in L$2\}$

$1.$ Specify an example language A over $\backslash$Sigma $1$ such that A $=$ and yet Substring$($A$)=,$ 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 $,$ or $(2)$ a sufficiently general and correct argument

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

$2.$ Specify example languages B$,$ C over $\backslash$Sigma $1$ such that B $=\backslash$Sigma $$

$1$ and C $=\backslash$Sigma $$

$1$ and yet B $$ C $=$

$\backslash$Sigma $$

$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 $\backslash$Sigma $$

$1,$ or $(2)$ a sufficiently general and correct

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

$3.$ Specify example finite languages L$1,$ L$2$ over $\backslash$Sigma $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.

$2$This means your solution will be evaluated not only on the correctness of your answers, but on your ability

to present your ideas clearly and logically$.$ You should explain how you arrived at your conclusions, using

mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument

for why something is true, your answers should always be well$-$supported. Your goal should be to convince the

reader that your results and methods are sound.

Copyright Mia Minnes, $2024,$ Version January $18,2024(4)$