1
$\begingroup$

I've been working on finding a regular expression for the following language for quite some time now ($\Sigma =\text{{0, 1}}$):

$ \text{L = {w | the difference between the number of 0's and 1's in each prefix of the word is less than or equal to 1}}$

I haven't been able to find an expression for this particular language so far, so I was wondering if the language is regular at all.

The following came to mind, but I'm pretty dubious about its validity :

Since $010$ belongs to said language, and by concatenation $010010$ does not, it would follow that this language isn't closed under Kleene star, hence it's not regular.

Am I wrong? If so, could you help with finding the solution to this problem?

Regarding the meaning of prefix in this context, the prefixes of the string $abcd$ are $\text{{$abcd, abc, ab, a$}}$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Don't confuse "the set of regular languages REG is closed against Kleene star" with "every regular language is closed against Kleene star". $\endgroup$ – Raphael♦ Oct 13 '16 at 13:43
  • $\begingroup$ You might be interested in this question: cstheory.stackexchange.com/questions/4254/…. $\endgroup$ – Yuval Filmus Oct 13 '16 at 17:26
5
$\begingroup$

No, your argument is not correct.

The "hence it's not regular" doesn't follow. Not every regular language is closed under Kleene star. Some regular languages aren't closed under Kleene star. I think you've misunderstood the closure property: the closure property states "If $L$ is regular, then $L^*$ is regular". Note that you can still have a regular language where $L \ne L^*$.

To learn how to solve this question correctly, you may want to check out our reference questions. See especially How to prove a language is regular?, Show whether the language with almost as many 0 as 1 in every prefix is regular, Language where every prefix has almost equal a's and b's.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Easy example: all finite languages are regular, but none of them are closed against the Kleene star. (As a matter of fact, take any language closed against KS, remove a single, well-chosen string, and you end up with a language of the same complexity (for most classes, that is) that is not closes against KS.) $\endgroup$ – Raphael♦ Oct 12 '16 at 22:01
3
$\begingroup$

The language $L'=\{1\}$ is not closed under the Kleene's star (e.g. $11\not\in L'$), but is regular (use a FSA with two states).

The closure property states that when $L''$ is regular, then $L''^*$ (which is another language) must be regular as well. It does not imply $L''^* = L''$.

For your language $L$, try writing a decider in your own favorite programming language. If it turns out that the decider's variables only assume finitely many values, you can convert that into a FSA, proving $L$ regular.

|cite|improve this answer
$\endgroup$

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.