Skip to main content
added 4 characters in body
Source Link

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$$\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$.

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

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

Post Undeleted by Daniel Donnelly
Post Deleted by Daniel Donnelly
Source Link

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