Regular Languages

Question

Let A = {a, b}, L = {a^nb^n:n>=1} and R = A*, then the languages RUL and R are:

a) Regular, Regular

b) Regular, Not Regular

c) Not Regular, Regular

d) Not Regular, Not Regular

Comments

a) both will be regular.

---

1st CFL union Regular -- Regular

2nd Regular.

---

Option a

Answer 1

R = {a, b}*

So it contains everything. And it is regular.

Now R U L is also R since whatever L be it will always be a subset of R(since it contains all possible strings).

So both the languages are same i.e. {a, b}* . Hence, both are regular.

And by the way, L is DCFL.

Answer 2

First of all L is DCFL. Not regular.

Now R is {a,b}*  So regular.
So it contains everything.
Now everything Union Something = Everything.
Everything is Regular.

So RUL & R both are regular.

Comments

Good explanation in simple language and easy way.