Take the 2-minute tour ×

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.

share|improve this question
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. –  Denis Jul 6 '12 at 0:41

2 Answers 2

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.

share|improve this answer
Sorry about the LaTeX failure in the second line. I don't know what that's about. –  Tara Brough Jun 7 '12 at 19:11
You need backquotes to escape math code in certain cricumstances, as indicated in the box that should be on the right or in the FAQ. I fixed it. –  Dylan Thurston Jun 7 '12 at 22:57
@Dylan: Thanks for fixing it! I think I used to know about that, but I haven't written anything on mathoverflow for a long time, so I forgot. –  Tara Brough Jun 8 '12 at 8:24

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.

share|improve this answer
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. –  Victor Mar 13 '12 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. –  Victor Mar 13 '12 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? –  user22116 Mar 13 '12 at 17:56
Locally testable is a good thing to look at, thanks! –  Victor Mar 14 '12 at 8:59

Your Answer


