1.5k views

Consider the following languages:

• $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$
• $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$
• $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$
• $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$

Which of the languages are regular?

1. Only $L1$ and $L2$
2. Only $L2, L3$ and $L4$
3. Only $L3$ and $L4$
4. Only $L3$
edited | 1.5k views

$L1=\{ww \mid w \in \{a,b\}^*\}\qquad$CSL

$L2=\{ww^R \mid w \in \{a,b\}^*,w^R \text{ is the reverse of w}\}\qquad$Palindrome, so CFL

$L3=\{0^{2i} \mid i \text{ is an integer}\}\qquad$Linear power and regular expression can be stated as $(00)^*$

$L4=\{0^{i^2} \mid i \text{ is an integer}\}\qquad$Non-linear power, so CSL

edited
0
As I tis given that set of strings in L3 will be integer....how does it behave for negative numbers?

L1 -> This is CSL

L2 -> This is CFL.

L3 -> This is regular. Regular expression (00)*

L4 -> This is CSL.

+1 vote
ans is D. only L3 is regular
0
Plz explain how L3 is regular..?

1
2