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.
 A: 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.
A: 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.
