Can one prove that a language is regular without having a regular expression?

Question

I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it.

For example: $L = \{w \in \Sigma^* : w \text{ has at least two identical letters} \}$

Answer 1

In this case it’s not hard to design a DFA that accepts the $L$.

For each $S\subseteq\Sigma$ give your DFA a state $q(S)$, and have one other state $q$ as well. Make $q(\varnothing)$ the initial state, and make $q$ the only acceptor state. For each $s\in\Sigma$ and $S\subseteq\Sigma$, the $s$-transition from $q(S)$ goes to $q(S\cup\{s\})$ if $s\notin S$ and to $q$ otherwise. All transition from $q$ are to $q$. It’s not hard to see that if you’re in state $q(S)$, you’ve seen each character in $S$ once; the moment you see a character a second time, you go to state $q$, and the word is accepted.

In general, however, the answer to your question is yes: there are ways to show that a language is regular without constructing a DFA, NFA, regular expression, or regular grammar for it, though only after one has proved some results that do use these methods. For example, if we know that $L_1$ and $L_2$ are regular, we can conclude that $L_1\cap L_2$ is regular, because the class of regular languages is closed under intersection. However, the proof of this fact uses one of the explicit characterizations.

Answer 2

There is an interesting example which relies on the notion of subword. A word $u$ is a subword of $v$ if $u$ can be obtained from $v$ by deleting some letters (not necessarily consecutive ones). For instance, $nesting$ is a subword of $i\color{red}{n}ter\color{red}{esting}$.

Now, take any language $L$ on the alphabet $A$ (regular or not) and let $R(L)$ be the language of all words of $A^*$ having at least one subword in $L$. Then one can show that $R(L)$ is always regular (this is a consequence of the fact that the subword order is a well quasi order), but there is no way to find a DFA for $R(L)$ if $L$ is, say, a non recursively enumerable language.

Answer 3

Yes you have several other techniques to show that a language is regular.

For instance you can show that the Myhill-Nerode equivalence has finite index, or you can exhibit a finite monoid recognizing your language.

You can also use a MSO sentence to describe your language, which may be the simplest way: for instance your language $L$ is recognized by the sentence $\exists x,\exists y\neq x, \bigvee_{a\in \Sigma} a(x)\wedge a(y)$, which is a proof that $L$ is regular.

This last method is convenient, since the MSO sentence is often quite close to the "intuitive" definition of your language: the above sentence just requires that there are two positions in the word labelled by the same letter, which is exactly how you defined your language in the first place.