Topology induced by context-free language

Question

Is there any way to reasonably define a topology on a context-free-language language? In other words, given a context-free grammar (or perhaps a grammar from an interesting subclass of context-free grammars), and a string generated by that grammar, can I reasonably define (and compute) other strings which are "the most similar" and can also be generated by this grammar?

EDIT: We could further assume that the CFG is equipped with some additional semantic structure, for example the denotational semantics of programming language it would define.

Answer 1

Take a look at the definition of regular grammars. The rules can be no more complex than $B \to aC$.

When studying topological groups it is sufficient to show that the maps $f(x) = gx$, for $g \in $ the group $G$ are continuous to prove that the group operation $G \times G \to G$ is then in fact continuous.

Now go back and look at regular grammars. See the connection? The rule or hom that replaces $B$ by $aC$ is of that form. So perhaps defining regular subsets of your CF language $L$ as open sets might suffice.

Also take a look at derivatives of regular expressions. These also relate because $u^{-1}S$ is how the derivative is expressed. That looks a lot like taking the inverse image of $f(x) = ux$!

Derivatives of regular expressions are themselves regular languages, and can be used for optimizing number of DFA states (AFAIC remember).

The reason we use regular languages for open sets was initially that CF languages are not generally closed under intersection.

---

Let $\Sigma_G$ be the alphabet of the grammar and $\Sigma$ the alphabet of $L$. There is a set of string homs $R = \{\varphi_i\}_{i=1\dots |G|}$ that correspond 1-1 with the grammar rules (the full set - without alternation "$|$"), and such that for every $s \in L$ there exists a sequence of compositions such that $\varphi_1 \circ \varphi_2 \circ \cdots \varphi_{n}(S) = s$, where $S$ is your start symbol. This sequence is not unique in general. For instance, let $\varphi(B) = aC$, and $\varphi= \text{id}$ elsewhere.

Clearly, this sequence of compositions is itself a string homomorphism from $\Sigma_G^* \to L$ and it can be made to fix $\Sigma^*$ (just like CFGs already do by definition).

A topology requires closure under arbitrary union. Good luck with that!

---

Thus, with the topologies of regular sublanguages as open sets, any string homomorphism is continuous as the inverse homomorphic image of a regular set is also regular. Therefore our "grammar rule homs" are continuous maps as well as any compositions of them where defined.

A corollary is that string concatenation $\cdot $ on $\Sigma'^*$ is a continuous operation, making each $\Sigma'^*$ mentioned above into a topological monoid.

Answer 2

I've written a little bit about closures in formal languages, which almost but not quite correspond to a topology:

Janusz Brzozowski, Elyot Grant, Jeffrey Shallit Closures in Formal Languages and Kuratowski’s Theorem http://link.springer.com/chapter/10.1007/978-3-642-02737-6_10 http://www.worldscientific.com/doi/abs/10.1142/S0129054111008052

E. Charlier, M. Domaratzki, T. Harju, and J. Shallit, Finite orbits of language operations, http://link.springer.com/chapter/10.1007%2F978-3-642-21254-3_15

Answer 3

Let $L$ be the context-free language, and $G$ a grammar that generates it. Let $\Sigma$ be your terminal alphabet, and $\Sigma_G = \Sigma \cup V$, where $V$ is the grammar's non-terminals.

A general CF grammar $G$ can be represented by a multi-valued string hom $\varphi: \Sigma_G^* \to \Sigma_G^*$ such that the union of all iterates of $\varphi$ at $S$ covers $L$. For example: $G = \{S\to aS; \ S \to a\}$ can be associated with $\varphi(S) = \{aS, a\}$.

These homs can be used to define open balls in $L$:

Define an open ball around a string ("point") $x \in L \subset \Sigma_G^*$ to be $$ B(x, \varphi) = \{y \in L: y \in \varphi(x)\} = L \cap \varphi(x) $$

How far away $\varphi(x)$ is from $x$ is encoded in how a particular $\varphi$ is defined.

If $B(x, \varphi) = \{y, z, w\}$ and $B(a, \psi) = \{z, w, b\}$, then define $\phi(S) = z, w$, so that these balls form a basis for a topology on $L$.