in Theory of Computation recategorized by
13,874 views
26 votes
26 votes

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
in Theory of Computation recategorized by
13.9k views

5 Answers

28 votes
28 votes
Best answer

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.

edited by
by

4 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={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.      

1
1
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 ?
0
0
Yes, this question is a good example of that limitation.
0
0
12 votes
12 votes

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

4 votes
4 votes

option c is right.

 

edited by

1 comment

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

4 Comments

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

@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 =?

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

Related questions