GATE CSE 2008 | Question: 53

Question

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\}$

• A. I and IV only
• B. I and III only
• C. I only
• D. IV only

Comments

in $IV$  ,    $c$  doesn’t belong to the symbol .

Then how is this regular?

---

@Pranavpurkar Must be a typo. It should be mentioned.

---

@Pranavpurkar

They have not defined any alphabet set
In option $C$ they have just mentioned that $x \ and\ y$ are any string on alphabet set ${a ,b}$

Answer 1

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.

Comments

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

---

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

---

@Shubham Aggarwal the language is basically any no of a’s followed by even no of b’s

Answer 2

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)$^{*}$.