# Infinite sequence has $m$ consecutive digits – regular languages

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?

• 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. – Gilles 'SO- stop being evil' 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$$.