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

ignougroup
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$: tree with before and after sets
[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 Atobeta in delta } cup {N_A to A mid Ain N}$

with $alpha(t)=t$ for all $t in T$ and $alpha(A)=N_A$ for all $ain 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 (Ncup T)^*$ are $mathcal{L}(beta(Ncup T)^*)$ and $mathcal{L}((Ncup 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}((Ncup T)^*beta)),/,beta in mathrm{CFL}$ and $qquad displaystyle operatorname{After}(beta) = (operatorname{Suff}(operatorname{SF}(G)) cap mathcal{L}(beta(Ncup 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

Leave a Reply