in Theory of Computation edited by
6,155 views
28 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
in Theory of Computation edited by
6.2k views

3 Comments

Why iv is regular anyone explain
0
Cz u can have a regular expression for iv

(a+b)*c(a+b)*
0

But by pumping lemma it can be shown that a^n b^2m is not regular. Please correct me if I'm wrong.

0

Subscribe to GO Classes for GATE CSE 2022

2 Answers

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

edited by

7 Comments

if option D were
 xcx then both x,c should belong to (a+b)* , right ?
1
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) *IS* regular. The regular language for d) will be (a+b)*c(a+b)*
7
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.

0

But by pumping lemma it can be shown that a^n b^2m is not regular. Please correct me if I'm wrong.

0
0 votes

I)Set of all strings containing any number of ‘a’ s followed by an even number of ‘b’ s. R.E=(a)$^{*}$(bb)$^{*}$.

IV) Strings containing a ‘c’. R.E= (a+b)$^{*}$c(a+b)$^{*}$.

Both these languages are regular as regular expressions exist.

By default a language is infinite. Eg : {a$^{n}$} it’s a infinite language.So both the languages II and III are infinite and comparison has to be done to evaluate these and hence are not regular.

 Answer: A


NOTE:

Every finite language is regular.

Infinite language + Comparison = Non-Regular.

Infinite language + No Comparison = Regular.


Edit: As nothing is mentioned about ‘c’ in option IV and there is a comma after y, So I think It’s a typo ‘c’ should also belongs to {a,b}$^{*}$. IV will be a complete language. Which is regular. R.E=(a+b)$^{*}$.

edited by
Answer:

Related questions