1.8k 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.8k 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
+1
As I tis given that set of strings in L3 will be integer....how does it behave for negative numbers?
0
What about negative no  in integers

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

L1, L2 are not Regular because we can't compare strings in Finite Automata. L1 is CSL, L2 is CFL

L3 is Regular because strings generated by L3 are even no of 0's.

L4 is not Regular because we can't design FA.

1
2