Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \{0,1,2,3,4,5,6,7,8,9\}$, let $L_k = \{m\geq 0: \text{$w$ contains a run of $m$ $k$'s}\}$ be a language. Here a run denotes a contiguous block of the sequences. Prove that $L_k$ is a regular language.

Here is my idea. Clearly, if $w$ contains arbitrarily long runs of $k$, then $L_k$ is pretty much just the set of all positive natural numbers, which is regular. But if $w$ has a maximum run of $k$'s, then $L_k$ is a finite set, which means it's regular. This is as far as I got, this language "feels" like it shouldn't be regular, but I am told it is. Would the regularity of $L_k$ even depend on whether it is possible to compute whether $w$ has a maximum run of $k$'s?

  • 2
    $\begingroup$ Please do not delete a question once it has been answered. That's rude towards the answerer and to other people who might be interested in the answer. $\endgroup$ – Gilles Feb 1 at 12:06

You don't explain how the input to $L_k$ is encoded, but $L_k$ will be regular under any reasonable encoding.

Indeed, if $w$ contains a run of $m$ many $k$'s, then it also contains a run of $m'$ many $k$'s for any $m' \leq m$. Therefore either $L_k$ is finite (indeed, of the form $\{0,\ldots,m\}$) or it consists of all of $\mathbb{N}$.

You seem to be troubled by the fact that $L_k$ is not necessarily computable from (a description of) $w$. But there is absolutely no such requirement – all we have to show is that for each $w$, the languages $L_k$ are regular. We are not claiming that we can compute $L_k$ from (a description of) $w$.


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.