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

$\endgroup$
2
  • $\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, 2016 at 13:43
  • $\begingroup$ You might be interested in this question: cstheory.stackexchange.com/questions/4254/…. $\endgroup$ Oct 13, 2016 at 17:26

2 Answers 2

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.

$\endgroup$
1
  • 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, 2016 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.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .