The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.6k 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 in Theory of Computation by Veteran (59.7k points)
edited by | 1.6k views

1 Answer

+19 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
0
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)
0
d) option is we cannot accept a string before checking w before c and y after c and this requires LBA. Hence d) is CSL and not regular.
+4
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?
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

44,493 questions
49,944 answers
165,713 comments
65,911 users