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

Improve this question
$\endgroup$
2
  • $\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. ♦
    Commented Nov 21, 2015 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
    Commented Nov 22, 2015 at 17:53

1 Answer 1

Reset to default
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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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