+21 votes
2k views

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
edited | 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
+1
if option D were
xcx then both x,c should belong to (a+b)* , right ?
0
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
0
@Leensharma can you explain option d)
+5
d) *IS* regular. The regular language for d) will be (a+b)*c(a+b)*
0
can you explain how 1st is regular by some explanation?
0

@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.

Answer:

+24 votes
5 answers
1
+32 votes
4 answers
2
+32 votes
4 answers
3
+18 votes
1 answer
4
+16 votes
3 answers
5
+17 votes
2 answers
6
+28 votes
5 answers
7