13,874 views

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

1. regular, regular
2. not regular, regular
3. regular, not regular
4. not regular, not regular

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.

by

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={am bn, m=n} is another way of writing R (L1=R). Now let L2 ={am bn | 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={am bn} 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. 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

by

option c is right. ### 1 comment

That was the way even I approached this question and the method seems to be a concrete one too.
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.

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

### 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 -

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

but how to deal with L U R =?

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