2,708 views

Consider the following languages:

$L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$

$L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$

Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are $\text{TRUE}?$

1. $L_{1}$ and $L_{2}$ are regular.
2. $L_{1}$ and $L_{2}$ are context-free.
3. $L_{1}$ is regular and $L_{2}$ is context-free.
4. $L_{1}$ and $L_{2}$ are context-free but not regular.

$L_1 :$

If $n>=0$ then the language $L_1$ contains ALL strings i.e. $L_1 = \{a,b \}^*$

if $n>=1$, the language $L_1$ contains ALL and ONLY the strings that start and end with $”a”$ i.e. Regular expression of $L_1 = a(a+b)^*a$

If $n>=k$, for some constant $k,$ the language $L_1$ contains ALL and ONLY the strings that start with $k$ $a's$ and end with $k$ $a's.$ i.e. Regular expression of $L_1 = a^k(a+b)^*a^k,$ where $k$ is some constant.

In any case, $L_1$ is Regular. Every regular language is CFL. So, $L_1$ is regular, as well as CFL.

In theory of computation, by default, range of any variable $n$ can be assumed to be $n>=0$. Since range of $n$ is not given in the question, So, we can assume it to be $n>=0$ (Some standard books of Theory of Computation mention that if nothing is mentioned about a variable $n$, then it can be assumed to be $n>=0$)

$L_2 :$

$L_2 = \{ wxw^R | |w| >0, |x| >0, w,x \in \{ a,b\}^* \}$

Every String, with at least 3 symbols, that starts and end with same symbol, is in $L_2$ (We can take $w$ as the first symbol, and $w^R$ will be the last symbol, remaining substring will be $x$)

Every string in $L_2$ has at least 3 symbols in it and starts and ends with same symbol(We can take $w$ as the first symbol, and $w^R$ will be the last symbol, remaining substring will be $x$).

So, $L_2 = [a\{a+b \}^+a] + [b\{a+b \}^+b]$

Since we have regular expression to describe $L_2,$ So, $L_2$ is Regular, as well as CFL.

@Deepak Poonia Sir, can’t we say that L1 is a subset of L2?

@Abhrajyoti00

By default, $n \geq 0,$ So, $L_1$ is $\Sigma^*,$ So, $L_2 \subseteq L_2$

@Deepak Poonia Sir, Yes, I mean L2 is a subset of L1.

In $L1$ since $w$ is (a+b)*, we can always put n=0 and L1 will be just (a+b)* So $L1$ is regular.

In $L2$  since x can take (a+b)* so it will include every alphabet except first and last alphabet so the language will just become set of strings that starts and ends with the same symbol, that is also regular,

From above two conclusion option A is correct.

Every regular language is also CFL from this option B and C is also correct. Option D is wrong.

by