The Gateway to Computer Science Excellence
+16 votes

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$
in Theory of Computation by Veteran (52.2k points)
edited by | 2.2k views

4 Answers

+19 votes
Best answer
$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

Therefore, answer is option D.
by Boss (16.5k points)
edited by
As I tis given that set of strings in L3 will be does it behave for negative numbers?
What about negative no  in integers
why we can't consider L4 as 0* ?
coz $L_4$ will not contain $000$ only contains exponential number of 0s.


Is L4 really a CSL or it should be Recursive Enumerable?

it is CSL


Is this argument correct

Pallindrome, so CSL

I know since its palindrome. Hence, you can use stack but saying that way doesn't seem logically correct.

Don' you think so?


Its correct.

all Palindrome strings can be detected with help of 1 stack.

hence it is a CFL

all CFL are CSL

so it should be correct.

Why do you think it is incorrect ?

+4 votes

L1 -> This is CSL

L2 -> This is CFL.

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

L4 -> This is CSL.

Answer -> D

by Boss (41.9k points)
+1 vote
ans is D. only L3 is regular
by Loyal (8.1k points)
Plz explain how L3 is regular..?
0 votes

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.

by Junior (983 points)
L = w.(w reverse)* | w € {a, b}*?

Please solve this... Is it regular or non regular??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,271 answers
104,788 users