Regular language - Theory Of Computing

Regular language – Theory Of Computing

A – L1 and L2 only

B – L1 and L3 only

C – L1 only

D – L2 only

E – None of the above

Show Answer With Best Explanation

Answer – E
Explanation:
Since, Regular Language doesn’t have memory .So, it doesn’t have capacity to hold anything.

In L1, in order to calculate a^źZ we have to first calculate z^z & store the value in memory then need to calculate power of a. but we already known that Regular Language doesn’t have capacity to hold anything. So, L1 is not regular language.

In L2, again we have to calculate zź , then store it & then need to find power of a. So, L2 is also not regular language.

In L3, we have to compare first ω with second ω. But, Regular Language doesn’t have capacity to compare two string. So L3 is also not regular language.

Question 2 UGC NET June-2020
Let L1 and L2 be languages over Σ =(a,b) represented by the regular expressions (a* + b)* and (a+b)* respectively.
Which of the following is true with respect to the two languages?

A – L1 ⊂ L2

B – L2 ⊂ L1

C – L1 = L2

D – L1 ∩ L2 = ɸ

Show Answer With Best Explanation

Answer : C
Explanation:
L1 = (a* + b)*
= {€, a, b, aa, ab, ba, bb…..} (generate all string possible over alphabet a,b)
L2 = (a + b)*
= {€, a, b, aa, ab, ba, bb…..} (generate all string possible over alphabet a,b)
L1 ==L2
(a+ b)* = (a+b) = (a+b) = (a+b)* = (ab)* = a(ba)* = b(ab)*