Let $L$ be a regular language over alphabet $\Sigma$ and let $A:=(Q,\Sigma,\delta, q\_0, F)$ be the minimal DFA recognizing $L$. For every $w\in \Sigma^\*$ define the variation of $w$ w.r.t. $L$ by 


$$\mathrm{Var}\_L(w) := \#\{0\leq k < n \text{ s.t. } \delta(w\_1\cdots w\_k)\neq \delta(w\_1\cdots w\_{k+1})\},$$
if $w:=w\_1\cdots w\_n$.


We say $L$ is of finite variation if $\sup\_{w\in\Sigma^\*}\{\text{Var}\_L(w)\}<+\infty$.


This should be equivalent to ask that the only cycles of $A$ are of length one (i.e., self-loops). 


Now what else can be said about the class $\text{FV}$ of regular languages with finite variation? Is there a characterization in terms of regular expressions? Is there a characterization in terms of generating elements (under boolean operations)?


I can prove that $\text{FV}$ is a $\*$-variety of Eilenberg, i.e. it is closed under boolean operations, left and right word quotients and inverse homomorphisms. By Eilenberg variety theorem there is an associated pseudovariety of monoids $M(\text{FV})$. Is there anything in the literature about $\text{FV}$ and $M(\text{FV})$? 


What if we consider the literally idempotent closure of $\text{FV}$?


Much more important: is any of this questions non-trivial to experts? :-)



Finite variation and idempotent languages and automata
It seems to me that FV should be the variety of languages associated to $\mathcal R$-trivial monoids. A monoid is $\mathcal R$-trivial if Green's relation $\mathcal R$ is trivial. This is the same as satisfying $(xy)^{\omega}x=(xy)^{\omega}$ for all $x,y$ where $z^{\omega}$ is the idempotent power of $z$. 


Suppose first that the language has finite variation. Then as you observed each oriented cycle must visit one vertex. In particular if $n$ is such that $(xy)^{\omega}=(xy)^n$, then there is a cycle at $q(xy)^n$ labeled by $(xy)^n$ for any state $q$. It follows that $x,y$ label loops at $q(xy)^n$ and so $q(xy)^nx=q(xy)^n$. Since $q$ was arbitrary, it follows $(xy)^nx=(xy)^n$


Conversely, the variety of $\mathcal R$-trivial languages is generated by languages of the form $A\_1^\*a\_1A\_2^\*\cdots a\_{n-1}A\_n^\*$ where the $A\_i$ are subsets of the alphabet and $a\_i\notin A\_i$. The minimal automaton has $n$ states. The elements of $A\_i$ label loops at state $i$ and $a\_i$ goes from state $i$ to $i+1$. Clearly this language has finite variation.


**More conceptual argument (update):** Let me rephrase the above proof to make it self-contained. Recall a monoid $M$ is $\mathcal R$-trivial if $aM=bM$ implies $a=b$.



> 
> **Proposition.**
>  Let $L$ be a regular language. The following are equivalent.
> 
> 
> 1. $L$ has finite variation.
> 2. Each strong connected component of the minimal automaton of $L$ has a single vertex.
> 3. There is a total ordering on the states of the minimal automaton of $L$ such that $qa\geq q$ for all states $q$ and inputs $a$.
> 4. The syntactic monoid of $L$ is $\mathcal R$-trivial.
> 
> 
> 


**Proof:**  

(1) iff (2). If there is a nontrivial strongly connected component, then there is an oriented cycle $p$ visiting at least 2 vertices and with no repeated vertices. If $w$ is the label of $p$, then the words $w^n$ show that the variation is not finite. If all strongly connected components are trivial then the variation is bounded by the length of the longest loop edge-free path.


(2) implies (3). Removing the loop edges gives an acyclic digraph. Topologically sort the states. Then by construction (3) holds since loop edges fix you and all other transitions go up in the order.


(3) implies (4) This is well known and can be found in Pin's book. The functions satisfying $qf\geq q$ for all states $q$ form a submonoid. Suppose $u,v$ generate the same right ideal of the syntactic monoid, the $u=vx$ and $v=uy$ for some $x,y$. Thus for any state $q$ we have $qu=qvx\geq qv=quy\geq qu$. Thus $u=v$. 


(4) implies (2). Suppose that $q,q'$ are in the same strongly connected component. There are elements of the syntactic monoid such that $qu=q'$ and $q'v=q$. Then $q(uv)^n=q$ and $q(uv)^nu=q'$ for all $n$. Choose $n$ so that $(uv)^n$ is idempotent. Then $(uv)^n$ generates the same right ideal as $(uv)^nu$ and so they are equal. Thus $q=q'$. QED


