How to prove $\text{if } {B \subseteq A} \implies A^*B^* = A^*$

50 Views Asked by At

For context, A and B is a regular language, and related to Theory of Computation.

As the title says, it is so intuitive that $$ \text{if } {B \subseteq A} \implies A^*B^* = A^* $$

I don't know how to prove this formally. Is this an axiom or I'm missing some sort of key observation that can formally prove the statement?

The best I can do is:

We can see that $\{\varepsilon\} \in B^* \implies A^* \subseteq A^*B^*$.
We also know that $B \subseteq A \implies B^* \subseteq A^* \implies A^*B^* \subseteq A^*A^* = A^* $
This proofs $A^* \subseteq A^*B^* \wedge A^*B^* \subseteq A^* \implies A^*B^* = A^*$

But, I don't think that's good enough. Because I feel like it's missing something or it has something wrong. Is there any better way to prove this instead of the way I'm doing it right now?

1

There are 1 best solutions below

0
On

The essence of the proof is that $$A^*=A^*\{\epsilon \}\subseteq A^*B^* \subseteq A^*A^*=A^*.$$ Is this formal enough or do you want to break it down further into definitions?