The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

Which of the following are regular sets?

  1. $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$

  2. $\left\{a^nb^m \mid n =2m  \right\}$

  3. $\left\{a^nb^m \mid n \neq m \right\}$

  4. $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$

  1. I and IV only
  2. I and III only
  3. I only
  4. IV only
asked in Theory of Computation by Veteran (52.1k points)
edited by | 2k views

1 Answer

+20 votes
Best answer

Answer is A.

Since in option 2 and 3, $n$ is dependent on $m$, therefore a comparison has to be done to evaluate those and hence are not regular.

I and IV are clearly regular sets.

answered by Boss (19.9k points)
edited by
if option D were
 xcx then both x,c should belong to (a+b)* , right ?
how option d is regular here ? for this c should belong to (a + b)^(*) it is not as it will give only c on keeping x as epsilion
@Leensharma can you explain option d)
d) *IS* regular. The regular language for d) will be (a+b)*c(a+b)*
can you explain how 1st is regular by some explanation?

@Shubham Aggarwal I Think first can be written as -->(a)*(bb)* . Here both asterisks are independent of each other and can be thought as n and m.


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,811 questions
54,533 answers
75,562 users