Categorize the following languages in the strictest category possible. Note that,

Finite $$ Regular $$ CFL $$ Decidable $$ Recognizable $P({}^{**}).$ For the upper

bound design an appropriate algorithm $($eg$.$ regular expression, recognizer for

complement, decider etc.$),$ and for lower bound use the techniques from lec$-$

ture notes $($eg$.$ pumping lemma, reduction, diagonalization$).$ Just prove lower

bound against the class immediately below your characterization, no points will

be given for any other lower bound. Two points for the upper bound, and

two points for the lower bound $($for infinite regular languages, for the lower

bound argue that they are not finite$).$ For higher characterization partial points

will be given, but for lower characterization no points will be given $($since the

characterization will be entirely incorrect$).$

For any non$-$deterministic TM $M$ let's define $M_{NS}$ the TM that simu$-$

lates $M$ for at$-$most $n^2$ time on any computation branch and rejects if

no decision is made. Let are TMs such that

$\{$:$L(M_{NS})L(N_{NS})\}.$ Characterize $L_1.$ Note that, $L_1$ is a special version

of $\frac{?}{\text{b}\text{a}\text{r}}(E{Q}_{TM})$ with some major differences in the definition.

Solution:

Upper bound:

Lower bound:

$L_2=\{0^{k}x|k{1}^{{?}^{?}}$xin$\{0,1{\}}^{**}{?}^{{?}^{?}}|x|k\}$

Solution:

Upper bound:

Lower bound:

$L_3=\{s^k(s^k{)}^R|k{0}^{{?}^{?}}sin\{01,100\}\}$ where $x^R$ is the reverse string of

string $x.$

Solution:

Upper bound:

Lower bound:

$($in lexicographic ordering$)$