10
$\begingroup$

I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found?

Wikipedia has a bunch: https://en.wikipedia.org/wiki/Regular_language#Equivalent_formalisms

  • it is the language of a regular expression (by the above definition)
  • it is the language accepted by a nondeterministic finite automaton (NFA)
  • it is the language accepted by a deterministic finite automaton (DFA)
  • it can be generated by a regular grammar
  • it is the language accepted by an alternating finite automaton
  • it is the language accepted by a two-way finite automaton
  • it can be generated by a prefix grammar
  • it can be accepted by a read-only Turing machine
  • it can be defined in monadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)
  • it is recognized by some finite syntactic monoid $M$, meaning it is the preimage $\{w \in \Sigma^* | f(w) \in S\}$ of a subset $S$ of a finite monoid $M$ under a monoid homomorphism $f: \Sigma^* \to M$ from the free monoid on its alphabet
  • the number of equivalence classes of its syntactic congruence is finite. (This number equals the number of states of the minimal deterministic finite automaton accepting L.)

And I'm aware of a few more:

  • Language accepted by an NFA with edges labeled by regular expressions (traversing an edge consumes a sequence of characters matching that regular expression) [These are "nondeterministic generalized finite automata" in "Automata Theory and its Applications", Khoussainov & Nerode]
  • Languages generated by languages of the form $ A^* $ and $A^* cd A^*$ ($A$ a set of characters, $c,d$ arbitrary characters) under Boolean operations and characterwise maps [This is Theorem 3.6 from "Decision Problems of Finite Automata Design and Related Arithmetics" by Elgot]
  • First-order describable subsets of Büchi Arithmetic under a suitable translation
  • First-order describable subsets of the words on a finite alphabet with predicates for prefix and equal length, and unary operations tack-an-$a$-onto-the-end for each character $a$.

I imagine there are more I don't know about through connections with other branches of mathematics, or possibly through the connection between $\frac{1}{1-x} = 1+x+x^2+x^3+\cdots$ and $A^* = \epsilon + A + AA + AAA + \cdots$.

$\endgroup$
2
  • 2
    $\begingroup$ Single-tape TMs in time o(n log n) (important that this is little-oh). $\endgroup$ Feb 4 at 3:16
  • $\begingroup$ Does "circular" unification apply here? $\endgroup$
    – ShyPerson
    Feb 5 at 3:23

5 Answers 5

5
$\begingroup$

I know it is frowned upon to promote one's own results, but it turns out that I wrote an article precisely on this topic. So let me add a few characterizations of regular languages not already mentioned. The complete relevant references can be found in the bibliography of [1].

(1) Pumping Lemma. Several authors (Jaffe, Stanat and Weiss, Ehrenfeucht, Parikh and Rozenberg) have proposed extensions of the pumping lemma that characterise regular languages. The most powerful version was given by Varricchio:

Theorem. A language $L$ is regular if and only if there is an integer $m > 0$ such that, for all words $x$, $u_1, \ldots, u_m$ and $y$, there exist $i, j$ with $1 \leq i < j \leq m$ such that for all $k >0$, $$ xu_1 \dotsm u_{i-1}(u_i \dotsm u_j)^ku_{j+1} \dotsm u_my \in L \iff xu_1 \dotsm u_my \in L $$

(2) Periodicity and permutation. A languages $L$ is periodic if, for any $u \in A^*$, there exist integers $n, k > 0$ such that, for all $x,y \in A^*$, $xu^ny \in L \iff xu^{n+k}y \in L$. It is $n$-permutable if, for any sequence $u_1, \ldots, u_n$ of $n$ words of $A^*$, there exists a nontrivial permutation $\sigma$ of $\{1, \ldots, n\}$ such that, for all $x,y \in A^*$, $xu_1 \dotsm u_ny \in L \iff xu_{\sigma(1)} \dotsm u_{\sigma(n)}y \in L$. It is permutable if it is permutable for some $n > 1$.

Theorem (Restivo and Reutenauer). A language is regular if and only if it is periodic and permutable.

(3) Iteration properties. The book of de Luca and Varricchio (1999) contains many results about iterations properties. Here is an example

Theorem. A language $L$ is regular if and only if there exist integers $m$ and $s$ such that for any $z_1, \ldots, z_m \in A^*$, there exist integers $h,k$ with $1 \leq h \leq k \leq m$, such that for all $u, v \in A^*$, $$ uz_1 \dotsm z_mv \in L \iff uz_1 \dotsm z_{h-1}(z_h \dotsm z_k)^nz_{k+1} \dotsm z_mv \in L, $$ for all $n \geq s$.

(4) Well quasi-orders. A quasi-order (or preorder) on $A^*$ is a reflexive and transitive relation. A quasi-order $\leq$ is stable (or monotone) if, for all words $u, v, x, y$, the condition $u \leq v$ implies $xuy \leq xvy$. The connection with regular languages was first established by Ehrenfeucht, Haussler and Rozenberg (1983)

Theorem. A language is regular if and only if it is an upper set with respect to some stable well quasi-order on $A^*$.

(5) Formal series

Theorem (Restivo and Reutenauer 1984). A language is regular if and only if it and its complement are both supports of a rational series.

(6) Monadic second order logic. Characterizations using $\mathbf{MSO}$ were already mentioned, but let me add a consequence of Rabin's tree theorem. Consider the structure $(A^*, (S_a)_{a \in A})$, where each $S_a$ is a binary relation symbol, interpreted on $A^*$ as follows: $S_a(u,v)$ if and only if $v = ua$. Let $\varphi(X)$ be a monadic second order formula with a free set-variable $X$. We write $\exists! X\ \varphi(X)$ as a short hand for the formula $\exists X \Bigr(\varphi(X) \wedge \bigl(\forall Y\ [\varphi(Y) \rightarrow (Y = X)]\bigr)\Bigr)$. A language $L$ is said to be definable in $\mathbf{MSO}[(S_a)_{a \in A}]$ if there exists a monadic second order formula $\varphi(X)$ such that $L$ satisfies $\exists! X\ \varphi(X)$.

Theorem (Rabin) A language of $A^*$ is regular if and only if it is definable in $\mathbf{MSO}[(S_a)_{a \in A}]$.

(7) Second order logic. Some fragments of (non monadic) second order logic --- in the signature $\{S, (\mathbf{a})_{a \in A}\}$ --- also capture the regular languages.

A quantifier prefix is any word on the alphabet $\{\exists, \forall\}$. A quantifier prefix class is any set of quantifier prefixes. For any quantifier prefix $Q$, let $\Sigma_0^1(Q)$ (resp. $\Pi_0^1(Q))$ be the set of all formulas of the shape $\exists \mathbf{R}\ Q \varphi$ (resp. $\forall \mathbf{R}\ Q \varphi$) where $\mathbf{R}$ is a list of relations and $\varphi$ is quantifier free. For every $k \geq 0$, let $\Sigma_{k+1}^1(Q)$ (resp., $\Pi_{k+1}^1(Q)$) be the set of all formulas of the form $\exists \mathbf{R}\ \Phi$ (resp. $\forall \mathbf{R}\ \Phi$) where $\Phi$ is a $\Pi_k^1(Q)$ (resp. $\Sigma_k^1(Q)$) formula. Finally, for every quantifier prefix class $\mathcal{Q}$, let $\Sigma_k^1(\mathcal{Q}) = \bigcup_{Q \in \mathcal{Q}} \Sigma_k^1(Q)$.

The fragment $\Sigma_1^1$, also known as existential second order and frequently denoted by $\mathbf{ESO}$, was first explored by Eiter, Gottlob and Gurevich (2000).

Theorem. A syntactic fragment $\mathbf{ESO}(\mathcal{Q})$ captures the regular languages if and only if $\mathcal{Q}$ is a quantifier prefix class contained in $\exists^*\forall(\forall \cup \exists^*)$ whose intersection with $\exists^*\forall\{\exists, \forall\}^+$ is nonempty.

The fragments $\Sigma_k^1(\mathcal{Q})$, with $k \geq 2$, were explored by Eiter, Gottlob and Schwentick (2002).

Theorem. A syntactic fragment $\mathbf{ESO}(\mathcal{Q})$ captures the regular languages if and only if $\mathcal{Q}$ is a quantifier prefix class contained in $\exists^*\forall(\forall \cup \exists^*)$ whose intersection with $\exists^*\forall\{\exists, \forall\}^+$ is nonempty.

Finally, the fragments $\Sigma_k^1(\mathcal{Q})$, with $k \geq 2$, were also explored by Eiter, Gottlob and Schwentick.

Theorem. The fragments $\Sigma_2^1(\forall \forall)$ and $\Sigma_2^1(\forall \exists)$ capture the class of regular languages. Furthermore, for each $k \geq 0$, the fragments $\Sigma_k^1(\forall)$ and $\Sigma_k^1(\exists)$ only define regular languages.

For more information on this topic, the reader is invited to read the beautiful survey of Eiter, Gottlob and Schwentick (2010).

(8) Other examples can be found in [1], notably related to rewriting systems, but I would like to conclude with two beautiful results.

Theorem. (Kunc 2005) Let $K$ be an arbitrary language and let $L$ be a regular language. Then the greatest solution of the inequality $XK \subseteq LX$ is regular.

The situation is totally different for equations of the type $XK = LX$. Indeed Kunc (2007) has shown that there exists a finite language $L$ such that the greatest solution of the equation $XL = LX$ is co-recursively enumerable complete, thus very far from being regular!

[1] J.-É. Pin, How to prove that a language is regular or star-free?, Proc. LATA 2020, LNCS 12038 (2020) 68-88

$\endgroup$
4
$\begingroup$

Here are fun ones:

$\endgroup$
1
3
$\begingroup$

The following restrictions on Turing machines force them to recognize only regular languages:

$\endgroup$
2
$\begingroup$

A language is regular if and only if it is linearly separable by the DFA kernel, defined here:

How many DFAs accept two given strings?

This is Theorem 11 in https://www.sciencedirect.com/science/article/pii/S0304397508004581

$\endgroup$
2
$\begingroup$

I think this one may fit the bill:


A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series.


Definitions. Let $\Sigma$ be an alphabet and $\mathbb{K}$ be a semiring. A formal series $S$ is a function $S : \Sigma^* \to \mathbb{K}$. A coefficient of a string $s$, denoted $\kappa_s$, in $S$ is the image of the string $s$ under $S$. Indeed, $S = \sum_{s \in \Sigma^*} \kappa_s s$. The language consisting of set of strings with nonzero coefficients is called the support $\mathrm{supp}(S)$ of a series. The set of all formal series over $\Sigma^*$ taking coefficients in $\mathbb{K}$ is denoted by $\mathbb{K}\langle \Sigma^* \rangle$. A formal series $S \in \mathbb{K}\langle \Sigma^* \rangle$ is called $\mathbb{K}$ proper if the coefficient of the neutral element of $\Sigma^*$ vanishes, i.e. if $\kappa_{\mathrm e} = 0$. A matrix over $\mathbb{K}\langle \Sigma^* \rangle$ is said to be $\mathbb{K}$-rational if all of its entries are proper. A formal series $S \in \mathbb{K}\langle \Sigma^* \rangle$ is said to be recognisable if its coefficients can all be written as $$\kappa_s = \alpha \cdot \mu(s) \cdot \beta,$$ where for some $n \geq 1$ we have $\alpha \in \mathbb{K}^{1,n}$ and $\beta \in \mathbb{K}^{n, 1}$, and the mapping $\mu: \Sigma^* \to \mathbb{K}^{n, n}$ is a multiplicative homomorphism of monoids. The characteristic series $\mathrm{char}(L)$ of a language $L \subseteq \Sigma^*$ is the series $S \in \mathbb{B}\langle \Sigma^* \rangle$ whose coefficients equal either $0$ or $1$ where $$\kappa_s = \begin{cases}1 &\text{if $s \in L$}\\0 &\text{if $s \notin L$,}\end{cases}$$ for all $s \in \Sigma^*$.


One can find most of these terms and other results in [Niv69], [BR88], and, especially, [SS78].

$\endgroup$
1
  • $\begingroup$ Thanks! Are these mappings $\mu$ at all related to what Conway calls "Event Transition Matrices"? i.e. matrices $M$ such that $M_{i,j}$ is the sum of input characters taking state $i$ to state $j$, and so $M^n_{i,j}$ is the sum (with multiplicity) of words of length $n$ taking state $i$ to state $j$ and thus $M^*_{i,j} = \sum_n M^n_{i,j}$ is the sum (with multiplicity) of all words taking state $i$ to state $j$? $\endgroup$
    – TomKern
    Feb 23 at 1:01

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.