Dark Mode

1,735 views

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

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

Every string $Y$ can be written in form of $a^n w a^n, $ where $w \in \{ a,b \}^*.$ In any string $Y$, Simply take $n=0,$ and $Y = w.$

For example:

$Y = ab = a^0w a^0; where \,\, w = ab $

$Y = b = a^0b a^0; where \,\, w = b $

$Y = aa = a^0w a^0; where \,\, w = aa $

$Y = a^5 bb a^5 = a^0w a^0; where \,\, w = a^5 bb a^5 $

So, EVERY string belongs to the given language $L_1.$ Hence, $L_1 = \Sigma^*$ which is Regular language (Single State DFA can be created for it).

1

2 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**