in Theory of Computation retagged by
1,735 views
8 votes
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}?$

  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.
in Theory of Computation retagged by
by
1.7k views

2 Answers

9 votes
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.
selected by

3 Comments

In L1 how canwe compare the number of a’s as they have to be equal, how is L1 regular ?
0
0

@Rutuja Desai

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
1
Yes understood, thank you!
0
0
2 votes
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

Answer:

Related questions