1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 21 '15 at 22:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Hendrik Jan Nov 22 '15 at 17:53
2
$\begingroup$

Hint: Suppose that as you read a word, you keep a counter which increases by 1 whenever you encounter 011, and decreases by 1 whenever you encounter 110. Show that the counter only gets the values 0,1,-1. In other words, between two occurrences of 011 there is an occurrence of 110, and vice versa. Use this to design your regular expression (you could also start with a DFA).

$\endgroup$
  • $\begingroup$ Why must the counter stay bounded? $\endgroup$ – Nathan FD Nov 22 '15 at 15:26
  • $\begingroup$ I'm not going to answer that. $\endgroup$ – Yuval Filmus Nov 22 '15 at 15:27
  • 1
    $\begingroup$ Ah I looked more closely at the form of the substrings. Good call. $\endgroup$ – Nathan FD Nov 22 '15 at 15:48

Your Answer

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

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