The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+10 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
asked in Theory of Computation by Veteran (68.8k points)
edited by | 1.1k views

3 Answers

+15 votes
Best answer

L1={ww∣w∈{a,b}∗}   CSL

L2={wwR∣w∈{a,b}∗,wR is the reverse of w}  Palindrome so CFL

L3={02i∣ i is an integer}          Linear Power and regular expression can be stated as $(00)^*$

L4={0i^2∣ i is an integer}             non linear power So CSL

Therefore answer is option D


answered by Veteran (15.8k points)
selected by
+3 votes

L1 -> This is CSL

L2 -> This is CFL.

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

L4 -> This is CSL.

Answer -> D


answered by Veteran (48.6k points)
+1 vote
ans is D. only L3 is regular
answered by Boss (8.5k points)
Plz explain how L3 is regular..?

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

32,620 questions
39,267 answers
36,655 users