<p>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 <em>stable</em> if it is closed under left quotient.</p>

<blockquote>
  <p>A language is context-free iff it belongs to a finitely generated
  stable algebra.</p>
</blockquote>

<p>[1] Berstel, J.; Boasson, L. <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1996AlgebraicTheory.pdf" rel="nofollow noreferrer">Towards an algebraic theory of context-free languages</a>. <em>Fund. Inform.</em> <strong>25</strong> (1996), no. 3-4, 217--239. </p>

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

CC BY-SA 3.0
2017-11-30T17:58:50.767Z
2017-11-30T18:20:43.350Z
2017-11-30T18:20:43.350Z
J.-E. Pin
<p>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$.</p>

<p>Want to define:</p>

<ul>
<li><p>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|}}$.</p></li>
<li><p>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)$</p></li>
</ul>

<p>An equivalent definition is:</p>

<ul>
<li>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$.</li>
</ul>

<p>Applied to formal languages:</p>

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

<p>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.</p>

<p>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$.</p>

<p>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.</p>

<p>Does anybody know</p>

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

<p>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.</p>

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

<p>I have posted this question on <a href="https://math.stackexchange.com/questions/2538018/is-this-generalization-of-context-free-grammars-known-and-strict">math.stackexchange</a> without any response.</p>

CC BY-SA 3.0
2017-11-30T12:59:33.363Z
I am not sure to understand your definitions. $\mathcal{S}$ defines a semigroup morphism from $\{1, \ldots,k\}$ to $\mathscr{P}(N)$. But then, what means $m = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$? Do you mean $M = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$?
J.-E. Pin
CC BY-SA 3.0
2017-11-30T16:57:34.653Z
$M$ is a set of sets! It is $m \in \mathscr{P}(N)$ and as such, $m = \mathcal{S}(w_1) \cup ... $ does make sense, as $\mathcal{S}(w_i)$ are also elements of $\mathscr{P}(N)$.
Henning
<fl.formal-languages><context-free>
Is this generalization of context free grammars known and strict?
Henning
# Is this generalization of context free grammars known and strict?

(Asked by: username_0 on 2017-11-28)

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](https://math.stackexchange.com/questions/2538018/is-this-generalization-of-context-free-grammars-known-and-strict) without any response.

**Tags:** fl.formal-languages, context-free

> **Comments:**
> **username_1**: I am not sure to understand your definitions. $\mathcal{S}$ defines a semigroup morphism from $\{1, \ldots,k\}$ to $\mathscr{P}(N)$. But then, what means $m = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$? Do you mean $M = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$?  
> **username_0**: $M$ is a set of sets! It is $m \in \mathscr{P}(N)$ and as such, $m = \mathcal{S}(w_1) \cup ... $ does make sense, as $\mathcal{S}(w_i)$ are also elements of $\mathscr{P}(N)$.  

---

## 1 answers

### Answer by username_1 on 2017-11-30. Score: 4 | Accepted answer

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](http://www-igm.univ-mlv.fr/~berstel/Articles/1996AlgebraicTheory.pdf). *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.


---

