retagged by
7,036 views
24 votes
24 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}?$

  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.
retagged by

2 Answers

Best answer
24 votes
24 votes
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.
selected by
6 votes
6 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

Answer:

Related questions