Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
    
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
1  
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
1  
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
show 6 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.