7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)$? $\endgroup$
    – J.-E. Pin
    Nov 30, 2017 at 12:59
  • $\begingroup$ $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)$. $\endgroup$
    – Henning
    Nov 30, 2017 at 16:57

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.