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 (52k points)
edited by | 1.8k views

4 Answers

+16 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.
answered by Boss (16.1k 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* ?
+4 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 (41k points)
+1 vote
ans is D. only L3 is regular
answered 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.

answered by Junior (847 points)

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
49,541 questions
54,071 answers
70,978 users