The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 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 (59.4k points)
edited by | 1.3k views

3 Answers

+16 votes
Best answer

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

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

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

$L4=\{0^{i^2} \mid i \text{ is an integer}\}$              non linear power So CSL

Therefore answer is option D

answered by Boss (15.6k points)
edited 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 Boss (42.4k points)
+1 vote
ans is D. only L3 is regular
answered by Loyal (8.3k 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

34,770 questions
41,730 answers
41,381 users