# Certain type of regular languages

Dear All,

there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that would be great.

So, our languages $L\subseteq (a+b)^*$ are defined as follows:

(0) First we choose some $n\geq 0$ and new letters $x_1,\ldots,x_n$ (if $n=0$, then we just basically don't choose any new letters);

(1) We choose words $w_i\in (a+b)^*$ for all $1\leq i\leq n$;

(2) Let $\phi$ be the homomorphism lifting the assignment $a\mapsto a$, $b\mapsto b$, $x_i\mapsto w_i$;

(3) Find a finite set $F$ from $(a+b+x_1+\cdots+x_n)^*$;

(4) Let $K=(a+b+x_1+\cdots+x_n)^{*}-(a+b+x_1+\cdots+x_n)^{*}F(a+b+x_1+\cdots+x_n)^{*}$

(5) Finally $L=\phi(K)$.

It is quite easy to see that $ba^+b$ cannot be obtained this way.

• I don't see why you need $\phi$ and the $x_i$'s, since $\phi((a+b+x_1+...+x_n)^*)=(a+b)^*$. If this is true (but I'm probably mistaking), then $L$ is just excluding a finite number of factors. Jul 6, 2012 at 0:41

I don't know if this will be helpful at all, but I came across something related to this in a talk by Jean-Eric Pin recently:

A language $L\subseteq A^*$ is called dense if for every word $u\in A^*$, we have $L\cap A^*uA^*\neq \emptyset$.

So your languages $K$ are nondense in $(a+b+x_1+\ldots+x_n)^*$. There are some results about nondense languages in Section 6.1 of this paper.

Hi Victor,

am I missing something or is this "just" the complement of a finite set of strings? The problem with regular expressions is that expressing the absence of patterns is not really straightforward (which is why some people prefer using logics such as MSO to specify these languages edit: This is not quite what I wanted to say. With regular expressions the absence of patterns can not be expressed neatly, but this is taken care of by just adding the complement. Global properties of strings are more nicely expressed in MSO though).

Obviously since the complement of $ba^+b$ is infinite, it cannot be obtained this way.

What is perhaps interesting about these languages is that any semigroup that recognises them (and equivalently any deterministic finite state automaton that recognises them) is the same as the one that recognises/accepts the finite complement, except for the set of accepting elements/states.

Maybe I am just missing something though.

• Hi Markus! Well, it's NOT the complement of finitely generated two-sided ideals: say, $L=(a+b)^*-(a+b)^*ab^+ab(a+b)^*$ is such that its complement is not finitely generated as a two-sided ideal, but nonetheless $L$ does appear via that procedure: we just take $n=1$, $x_1=x$, $F=\{ab,bx,ax^2\}$, and $\phi$ maps $x\mapsto ab$. It's quite tricky. Mar 13, 2012 at 16:56
• The thing about $ba^+b$ is the following: every language $L$ which appears in our procedure has the following property: there exist two numbers $n=n(L)$ and $k=k(L)$, with $k<n$, such that for every word $w\in L$ with $|w|\geq n$, there exists a subword $w'$ of the word $w$ which is obtained by cutting out at most $k$ letters such that $w'\in L$. Of course, $ba^+b$ does not possess this property. Mar 13, 2012 at 16:59
• I was being unattentive. I completely ignored the pre- and postmultiplication by (a+b+x1+...+xn)^*. You are still avoiding a finite set of patterns. I wonder whether there is some relationship with locally testable regular languages or other properties of the syntactic semigroup of those languages. Have you looked into that? Mar 13, 2012 at 17:56
• Locally testable is a good thing to look at, thanks! Mar 14, 2012 at 8:59