GATE CSE 1995 | Question: 2.24

Question

Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\} $ then the languages $L \cup R$ and $R$ are respectively

• A. regular, regular
• B. not regular, regular
• C. regular, not regular
• D. not regular, not regular

Answer 1

Answer is (C). $L \cup R$ is nothing but $L$ as $R$ is a subset of $L$ and hence regular. $R$ is deterministic context-free but not regular as we require a stack to keep the count of 0's to match that of $1$'s.

Comments

No Ashutosh, L is regular. WE can understand it as: - If R is a non-regular part of regular language L, then the other part of L ( After removing R from L : ' L - R' ) must also be non regular such that when R comes together with it, both these parts cancel out each other's non-regularity. eg.  L1={a^m bⁿ, m=n} is another way of writing R (L1=R). Now let L2 ={a^m bⁿ | m not equal to n }. Both L1 and L2 are non regular as both have infinite values of m,n and FA cant remember them. Now add L1 and L2. We get L1+L2={a^m bⁿ} i.e. no condition attached to m, n : all possible strings {a^m b^n} are accepted, which gives a regular language ,as L1 and L2 cancel each others non regularity when they come together.

But I think we can definitely say that if L is regular and R is a non regular subset of L then L- R is also a non regular subset of L.      

---

although i got answer, and also as R is subset of L making LUR as regular. Just a little doubt :

At the very first moment when i figure out R is CFL and L is regular then i applied closure property. By which i got LUR as not regular. Is this approach has some limitations ?

---

Yes, this question is a good example of that limitation.

Answer 2

Finally we can't guarantee that the union. intersection, subtraction or concatenation of this languages are irregular always.

for this question ,answer will be C

Source:https://cs.stackexchange.com/questions/49448/union-and-intersection-of-a-regular-and-a-non-regular-language

Answer 3

option c is right.

 

Comments

That was the way even I approached this question and the method seems to be a concrete one too.

Answer 4

It will be D.

Since L is regular and R is CFL. (L U R) is regular union... which results in the language union with regular. Since R is not regular, so its result will also be not regular.

Comments

U -- is for union. How can it give {01} ?

---

@Arjun I'm so sorry confused it with intersection or I don't know, what. 

Well, in your above comment you said identify the set of strings in the L in order to determine it's class and 

RL U N R.L is not ALWAYS regular.

and RL U N.RL is SOMETIMES regular.

So, in this question - L is regular as it's {0,1}* and R = {0^n1^n , n>0} is DCFL then what to do next in order to find what is 

L U R = ? 

set of strings can be - 

L = {e,0,1,00,01,10,11,. . .  .}

R = {01,0011,000111,........ }

but how to deal with L U R =?

---

$Note:- \text{when particular languages are given, never apply generic properties.}$