The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+19 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 (59.5k points)
edited by | 1.3k 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.7k 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) 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.
d) *IS* regular. The regular language for d) will be (a+b)*c(a+b)*

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

37,996 questions
45,492 answers
48,592 users