# Finding regular expression for a language with more substring of one type than from another

Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110.

I tried to figure out what would be the finite automata but I'm not to sure. I also tried to proof it isn't regular using Myhill-Nerode theorem but the problem is the language "readjusts" itself:

110011 (1 110, 1 011)

011110 (1 110, 1 011)

011011 (2 011, 1 110)

110110 (1 011, 2 110)

Now I'm convinced it should be regular but don't know how to proof it.

Edit:

¿Should be something similar to: $(0^{+}11^{+}+11^{+}0^{+})^{*}110(0^{+}11^{+}+11^{+}0^{+})^{*} + \epsilon$?

• Looks like a dup of cs.stackexchange.com/q/1331/755. Is there any reason this should not be closed as a duplicate of that question? In other words: We get asked this sort of question so often that we've written a reference questions with the techniques to use for this sort of problem. Please work through the material there, try to solve your problem again, and edit your question to include your attempts along with the specific problems you encountered.
– D.W.
Nov 21 '15 at 22:35
• @D.W. No it is not a duplicate of the question "is this language regular". This is a question with a twist, where just a little "aha insight" is needed before we can answer with the reference techniques. However, it is of course very similar to "Is the language of words containing equal number of 001 and 100 regular?". But that one is not easy to trace. Nov 22 '15 at 17:53