Can a non regular language be a subset of a regular language

$\begingroup$

If I have a Language A and A is not regular and A is a subset of B, then B can't be regular.

I think this is False. Because I can have B = {a^m b^n | m,n >= 0} A = {a^m b^m | m >=0 }

A is not regular and B is regular. And A is a subset of B. So it is possible for B to be regular.

I just a bit confused and want to know if this thought would be correct or not?

$\endgroup$

1 Answer

$\begingroup$

Your argument is correct, but there is a simpler example. Let $A$ be any nonregular language on a finite alphabet $\Sigma$. Then $A$ is a subset of $\Sigma^*$, but $\Sigma^*$ is regular.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy