[Solved]: Are the Before and After sets for context-free grammars always context-free?

Problem Detail: 

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the start symbol of $S$. Let $\operatorname{SF}(G)$ be the set of sentential forms of $G$.

Let $\alpha \in \operatorname{SF}(G)$ and let $\beta$ be a substring of $\alpha$ - we call $\beta$ a fragment of $\operatorname{SF}(G)$. Now let

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

and

$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$.

Are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ context-free languages? What if $G$ is unambiguous? If $G$ is unambiguous, are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ also describable by an unambiguous context-free language?

This is a followup to my earlier question, after an earlier attempt to make my question easier to answer failed. A negative answer will make the encompassing question I'm working on very hard to answer.

Asked By : Alex ten Brink

Answered By : Raphael

Let us get a feeling for $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ first. Consider a derivation tree which contains $\beta$; "contains" here means that you can cut away subtrees so that $\beta$ is a subword of the tree's front. Then, the before (after) set are all potential fronts of the tree's part left (right) of $\beta$:

^[source]

So we have to build a grammar for the horizontally lined (vertically lined) part of the tree. That seems easy enough as we already have a grammar for the whole tree; we just have to make sure all sentential forms are words (change the alphabets), filter away those that do not contain $\beta$ (that is a regular property as $\beta$ is fixed) and cut away everything after (before) $\beta$, including $\beta$. This cutting should also be possible.

---

Now to a formal proof. We will transform the grammar as outlined and use closure properties of $\mathrm{CFL}$ to do the filtering and cutting, i.e. we perform a non-constructive proof.

Let $G = (N, T, \delta, S)$ a context-free grammar. It is easy to see that $\operatorname{SF}(G)$ is context-free; construct $G'=(N',T',\delta',N_S)$ like this:

• $N' = \{N_A \mid A \in N\}$
• $T' = N \cup T$
• $\delta' = \{\alpha(A) \to \alpha(\beta)\mid A\to\beta \in \delta \} \cup \{N_A \to A \mid A\in N\}$

with $\alpha(t)=t$ for all $t \in T$ and $\alpha(A)=N_A$ for all $a\in N$. It is clear that $\mathcal{L}(G')=\operatorname{SF}(G)$; therefore the corresponding prefix closure $\operatorname{Pref}(\operatorname{SF}(G))$ and suffix closure $\operatorname{Suff}(\operatorname{SF}(G))$ are context-free, too¹.

Now, for any $\beta \in (N\cup T)^*$ are $\mathcal{L}(\beta(N\cup T)^*)$ and $\mathcal{L}((N\cup T)^*\beta)$ regular languages. As $\mathrm{CFL}$ is closed under intersection and right/left quotient with regular languages, we get

$\qquad \displaystyle \operatorname{Before}(\beta) = (\operatorname{Pref}(\operatorname{SF}(G))\ \cap\ \mathcal{L}((N\cup T)^*\beta))\,/\,\beta \in \mathrm{CFL}$

and

$\qquad \displaystyle \operatorname{After}(\beta) = (\operatorname{Suff}(\operatorname{SF}(G))\ \cap\ \mathcal{L}(\beta(N\cup T)^*))\,\backslash\, \beta \in \mathrm{CFL}$.

---

¹ $\mathrm{CFL}$ is closed under right (and left) quotient; $\operatorname{Pref}(L) = L / \Sigma^*$ and similar for $\operatorname{Suff}$ yield prefix resp. suffix closure.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/802