# Is one regular language subset of another?

Let $L_1$ and $L_2$ be two regular languages given as regular expressions (in this type of tasks it often happens that $L_1 \subseteq L_2$, but vice versa it is false).

Is there a nice way to prove that $L_1 \subseteq L_2$ ? If yes, than do you think you could explain that algorithm?

I had an idea to construct those languages from regexes using Kleene theorem and than prove that every word from $L_1$ can be a prefix or a suffix of some word w $\in$ $L_2$, where the rest of w can be omitted (i.e. in regex representation it is under $^*$ sign).

OK, another idea is to use brute force - just show step by step that any word from $L_1$ is accepted by the DFA corresponding to $r_2$. However, what if there are too many words in $L(r_1)$?

So I don't think these are good ideas.

Example: $$r_1 = (a+ab+bb)(a+b)^* \\ r_2 = aab^*$$ Obviously $L(r_1) \text { is not a subset of } L(r_2)$, but $L(r_2) \subseteq L(r_1)$.

-
You could convert both to FSMs and run them in parallel. –  Jan Dvorak Jan 21 '13 at 22:48
@Jan Dvorak, what do you mean by run in parallel? Draw on a piece of paper next to each other? –  petajamaja Jan 21 '13 at 22:49
FSM = Finite state machines? –  petajamaja Jan 21 '13 at 22:51
Basically, I want you to make a cartesian product of two deterministic finite state machines and see if any of the [accepts, rejects] or [rejects, accepts] states are accessible from the [start, start] state. –  Jan Dvorak Jan 21 '13 at 22:53
Umari, those stars are supposed to be superscripts; writing them on the main line is simply wrong. –  Brian M. Scott Jan 21 '13 at 22:54

## 1 Answer

The basic idea for an automated proof is:

• convert both languages to their deterministic finite state machines.
• Calculate the cross product of the finite state machines with the transitions $F: ([x,y],\sigma) => [F_x(x,\sigma), F_y(y,\sigma)]$
• Collect the list of reachable states, and their acceptivity status from both languages. If there are any
• [reject, reject] states, then the union of both languages is not the universal language (there is a word that they both reject).
• [reject, accept] states, then the latter is not a subset of the former.
• [accept, reject] states, then the former is not a subset of the latter.
• [accept, accept] states, then the languages are not disjoint.

Other classes: two languages are equivalent if they are both subsets of each other (however, there are other tests for that); One language is a proper subset of another language if it is its subset but not vice versa.

-
Great answer, thanks! –  petajamaja Jan 21 '13 at 23:17
@Umari Note that it might be beneficial performance-wise to combine the latter two steps. –  Jan Dvorak Jan 21 '13 at 23:18