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

Dark Mode

2,708 views

11 votes

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}?$

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

14 votes

Best answer

Answer : A,B,C

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

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

5 votes

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.

**Answer: A, B, C**