Regular languages that seem irregular

Question

I'm trying to find examples of languages that don't seem regular, but are. A reference to where such examples may be found is also appreciated.

So far I've found two. One is $L_1=\{a^ku\,\,|\,\,u\in \{a,b\}^∗$ and $u$ contains at least $k$ $a$'s, for $k\geq 1\}$, from this post, and the other is $L_2 = \{uww^rv\,\,|\,\, u,w,v\in\{a,b\}^+\}$, which is an exercise (exercise 19 from section 4.3) in An Introduction to Formal Languages and Automata by Peter Linz.

I suppose the aspect of seeming to be regular depends on your familiarity with the topic, but, for me, I would have said that those languages were not regular at a first glance. The trick seems to be to write a simple language in more complicated terms, like using $ww^R$, which reminds us of the irregular language of even length palindromes.

I'm not looking for extremely complicated ways of expressing a regular language, just some examples where the definition of the language seems to rely on concepts that usually make a language irregular, but are then "absorbed" by the other terms in the definition.

Answer 1

My favorite example of this, which is often used as a difficult/tricky exercise, is the language: $$L=\{w\in \{0,1\}^*:w \text{ has an equal number of } 01\text{ and }10\}$$ This has the strong flavor of the non-regular "same number of $0$ and $1$", but the alternation of $0$ and $1$ makes it regular nonetheless.

Answer 2

Here is another all time favourite language that looks very non-regular. All these questions refer to the same language.

Is the language of words with as many a's in the first as b's in the second part context-free?

Finite strings and relationships between words

DFA for the language L = { w=xy∈(a,b)∗∣|x|a=|y|b }

Is language {a,b}∗ same as language $\{\;xy\in \{a,b\}^∗ \mid |x|_a=|y|_b\;\}$?

How to check L is regular or not

Answer 3

For a different kind of example, consider the language consisting of the usual decimal representations of integer multiples of 7, namely $\{ \dots, -14, -7, 0, 7, 14, 21, 28, \dots \}$. This is a regular language. (And in fact, the same would be true with any other positive integer instead of 7; but 7 is a cool example because, unlike with the other small integers, there isn't a commonly-known way to tell if a string of digits represents a multiple of 7 other than doing the division and seeing if the remainder is zero.)

---

To see why this is a regular language, let's first focus on just decimal representations of positive integers. These representations can be grouped into seven sets: one for the multiples of seven (7, 14, 21, etc.), one for one plus a multiple of seven (1, 8, 15, etc.), one for two plus a multiple of seven (2, 9, 16, etc.), and so on. The important thing is that if we have a string $x$ representing a positive integer and a single digit $d$, then we can figure out which set $xd$ is in based only on $d$ and the set that $x$ is in. For example, if $...348$ represents two plus a multiple of seven, then $...3485$ has to represent four plus a multiple of seven (because if $...348$ represents $2 + 7n$ for some integer $n$, then $...3485$ represents $10(2 + 7n) + 5 = 25 + 7n = 4 + 7(n + 3)$). So we can create a DFA with a separate state for each of these sets (plus an initial state for the empty string), and simply set the "accept" state appropriately in order to have it detect decimal representations of positive multiples of 7.

Extending this to decimal representations of arbitrary multiples of 7 is straightforward; we just need an extra state for leading $0$ (which is an "accept" state with no outbound edges) and an extra state for a leading minus sign (which is equivalent to the initial state except that it doesn't have an outbound edge to itself or the $0$ state).

And likewise for any other positive divisors instead of 7, though obviously there are some divisors that can be handled with fewer states than that.

Answer 4

Multiples of three, expressed in binary, especially combined with a proof that powers of three, expressed in binary, is not a regular language. (Or in general: multiples of $n$ expressed in base $b$ are regular, whereas powers of $n$ expressed in base $b$ are a regular language iff there exist positive integral $p$ and $q$ such that $b^p = n^q$)

See also numbers (with decimal point, but finite expansion) written in base 10 greater than $x$. (or less than $x$) This is regular if and only if $x$ is rational. That "positive numbers with finite decimal representations less than $\sqrt{2}$" is not a regular language is probably not too surprising, but it might be surprising that "decimal numbers representing a value between $\frac{1}{7}$ and $\frac{2}{7}$" is regular.

Answer 5

You could get many examples from languages that are finite but don't look it. For example, the language of strings all of whose prefixes are decimal representations of prime numbers is regular because there are only 83 such strings (A024770).

The language of sequences of 0s that appear in the decimal expansion of $π$ is regular. It showed up in a different context in this question.

The language of finite substrings of the decimal expansion of Chaitin's Ω is regular because Ω is provably normal.