The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.7k 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$
asked in Theory of Computation by Veteran (59.8k points)
edited by | 1.7k 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
+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
+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 (43.4k points)
+1 vote
ans is D. only L3 is regular
answered by Loyal (8.1k points)
0
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 (331 points)
Answer:

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

46,786 questions
51,234 answers
176,575 comments
66,585 users