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 regular, regular not regular, regular regular, not regular not regular, not regular Theory of Computation gate1995 theory-of-computation easy regular-language + – Kathleen asked Oct 8, 2014 recategorized Apr 25, 2021 by Lakshman Bhaiya Kathleen 15.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 29 votes 29 votes 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. Arjun answered Oct 9, 2014 edited Mar 7, 2018 by kenzou Arjun comment Share Follow See all 6 Comments See all 6 6 Comments reply Gate Keeda commented Oct 9, 2014 reply Follow Share you mean in the above example, L is a subset of R? 0 votes 0 votes Arjun commented Oct 9, 2014 reply Follow Share Sorry, I put it otherway- corrected now. R is a subset of L. 0 votes 0 votes Asutosh commented Jun 24, 2018 reply Follow Share @Arjun if R is a part of L and R cant be represented in DFA or NFA, then it would mean that some part of L cant be represented in DFA or NFA. Thus some part of L is not Regular. Thus L has to be not regular 0 votes 0 votes aadhar commented Aug 2, 2018 reply Follow Share 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 votes 1 votes shaurya_narayan commented Oct 4, 2019 reply Follow Share 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 votes 0 votes ankit3009 commented Nov 20, 2021 reply Follow Share Yes, this question is a good example of that limitation. 0 votes 0 votes Please log in or register to add a comment.
14 votes 14 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 set2018 answered Oct 28, 2017 set2018 comment Share Follow See all 0 reply Please log in or register to add a comment.
6 votes 6 votes option c is right. abhishekmehta4u answered Mar 28, 2019 edited Mar 28, 2019 by abhishekmehta4u abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply ankit3009 commented Nov 20, 2021 reply Follow Share That was the way even I approached this question and the method seems to be a concrete one too. 0 votes 0 votes Please log in or register to add a comment.
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. Gate Keeda answered Oct 9, 2014 Gate Keeda comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Arjun commented Sep 5, 2017 reply Follow Share U -- is for union. How can it give {01} ? 0 votes 0 votes iarnav commented Sep 5, 2017 reply Follow Share @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 votes 0 votes Manu Thakur commented Nov 28, 2017 reply Follow Share $Note:- \text{when particular languages are given, never apply generic properties.}$ 3 votes 3 votes Please log in or register to add a comment.