TheoryofComputation
October 6, 2023TheoryofComputation
October 6, 2023TheoryofComputation
Question 6

Consider the following statements.
 I. If L_{1} ∪ L_{2} is regular, then both L_{1} and L_{2} must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
Both I and II


II only


Neither I nor II


I only

Question 6 Explanation:
Statement I is wrong.
Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Correct Answer: C
Question 6 Explanation:
Statement I is wrong.
Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Subscribe
Login
0 Comments