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

$\text{C is DCFL too.}$

 

---

Difference between Regular Set and Regular Language (TOC)

Regular set and regular language are equivalent terms; both denote a set of strings recognizable by a finite automaton or describable by a regular expression.

---

IV - $(a+b)^{*}c(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

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

---

@Payal1999 Pumping lemma says for all candidate strings w where |w| >=P (magical number) and w ∈ L ,

such that in the first P symbol  there exist some y for which $xy^nz$ ∈ L. 

Here , you have taken y as abb and after pumping it doesn't belongs to L, so take another y let's say a , now hwo many times you pump the string it belongs to L because Regex for L is $ a^* (bb)*$ .

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

Answer 3

Answer is A.
See below image for full explanation.

Answer 4

A.here we have to accept any number of a's and even number of b's  [a*(bb)* is our regular expression] hence it is regular

B.here number of b's are depending on number of a's  which can be infinite possibilities so dfa cannot count such infinite cases hence Non Regular language. But it is CFL since npda can easily with the help of non determinimism can accept it its not DCFL since non determinism is not allowed in DPDA .

C.it says a's and b's should not be equal hence infinite counting which cant be entertained by Our DFA hence non regular
now it is a cfl but not dcfl

D.its a language saying exaclty one c in hence its it regular,cfl,dcfl,recursive enumerable.