8
$\begingroup$

Question

Let $L$ be a regular language. Let's say we sort $L$ by length and then lexicographically; then let $L_p \subset L$ be every $p$th word in $L$ according to this sort. Is $L_p$ regular as well?

Example

For example, let's use $L = a^*b^* = \{\epsilon, a, b, aa, ab, bb, aaa, aab, abb, ...\}$. Then $L_2 = \{\epsilon, b, ab, aaa, abb, aaaa, aabb, bbbb, ...\}$, which is a regular language: $$L_2 = (aaaa)^*((\epsilon + b) + a(b + bb)+aa(bb+bbb)+aaa(bbb+\epsilon))(bbbb)^*$$

Put another way, $L_2 = \{a^mb^n \mid n = m \lor n = m+1 \mod 4\}$.

$\endgroup$

1 Answer 1

7
$\begingroup$

The answer is yes: Theorem 4 in "Numeration systems on a regular language" (Leconte and Rigo) shows that any arithmetic progression in a regular language is regular.

$\endgroup$
1
  • 2
    $\begingroup$ For future readers, the text is available on arXiv. $\endgroup$
    – Nathaniel
    Sep 4, 2022 at 7:31

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.