Is this generalization of context free grammars known and strict? Let $\Sigma$ be an finite alphabet and $(N, \circ)$ a semigroup. The semigroup operation on $N$ can be extended to $\mathscr{P}(N)$: $N_1 \circ N_2 := \{ \; n_1 \circ n_2 \; | \; n_1 \in N_1, \; n_2 \in N_2 \; \}$ for $N_1, N_2 \subseteq N$.

Want to define:


A finite set $\mathcal{S} := \{ S_1, S_2, ..., S_k \}$ with $S_i \subseteq N$ is called a finite system of $N$. For $w \in \{1, .., k\}^+$ we have the homomorphism $\mathcal{S}(w) := S_{w_1} \; \circ \; ... \; \circ \; S_{w_{|w|}}$.
A set $M \subseteq \mathscr{P}(N)$ has a finite generating set, iff there is a finite system $\mathcal{S}$ of $N$ so that $\forall m \in M: \exists w_1, ..., w_j \in \{1,...,|S|\}^+: m = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$


An equivalent definition is:


Consider the semiring $R := (\mathscr{P}(N), \cup, \circ)$.
A set $M \subseteq R$ has a finite generating set if there is a finite set $S \subseteq R$ so that every subsemiring of $R$ that contains $S$ also contains $M$.


Applied to formal languages:


Let $w^{-1}L := \{ \; v \; | \; wv \in L \; \}$ for a language $L \subseteq \Sigma^*$ and $w \in \Sigma^*$.
A language $L \subseteq \Sigma^*$ has a finite generating set, iff
$M_L := \{ \; w^{-1}L \; | \; w \in \Sigma^* \; \}$ has a finite generating set.


Clearly, all context free languages have a finite generating set. There are also languages that don't have a finite generating set, e.g. $L_1 := \{ \; w\#v \; | \; v, w \in \Sigma^*, \; v \not\in w^* \; \} $. This can be shown easily by using that $M_1 := \{ \; \mathbb{N}_0 \setminus k \mathbb{N} \; | \; k \in \mathbb{N} \; \}$ does not have a finite generating set.

For $\Sigma = \{ a, b \}$ and $L \subseteq \Sigma^*$ we have the identity: $w^{-1}L = \{ a \} \circ (wa)^{-1}L \; \cup \; \{ b \} \circ (wb)^{-1}L$.

As a fun fact: if we limit $j$ from the definition above to $1$ and consider infinite sets $M \subseteq \mathscr{P}(\Sigma^*)$ with $\forall m \in M: \varepsilon \in m$ that have a finite generating set, we can always find $m_1, m_2 \in M, \; m_1 \neq m_2$ so that $m_1 \subseteq m_2$. This is because the subsequence ordering on $\{ 1,...,|\mathcal{S}| \}^*$ is a well quasi ordering.

Does anybody know


whether this generalization of context free languages has been explored?
an example of a language that is not context free but has a finite generating set?
better terminology?


It seems obvious that languages with finite generating sets are more powerful than context free grammars (the elements of a finite system don't even have to be decidable), but I wasn't able to construct a counter example.

However, if $M_L$ itself is finite, $L$ is even regular and the sets of $M_L$ are decidable!

I have posted this question on math.stackexchange without any response.
I think the answer to your question can be found in Theorem 3.1 of [1], where it is credited to Wechler [2]. An algebra is stable if it is closed under left quotient.


  A language is context-free iff it belongs to a finitely generated
  stable algebra.


[1] Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages. Fund. Inform. 25 (1996), no. 3-4, 217--239. 

[2] Wechler, Wolfgang. Characterization of rational and algebraic power series. RAIRO Inform. Théor. 17 (1983), no. 1, 3-11.