Find a CFG for the set of prefixes of a CFL How do i generate grammar for Prefix  of Langauge L, SupposeG=(V,,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈∗ : ∃ y such that xy∈L}.

I understand for Suffix(L) we would do something like this .. Can someone here help me how do we do for the Prefix(L) if L is CFL.


For each variable X of G , add a new variable
X' . (X' will generate the suffixes of the language that is generated by using X as the start variable.)
Whenever X' →YZ is a rule of G , we add two new rules,X' →Y' Z and X' → Z' .
for each variable in G , we add
X' → X and X' → ε
If S is the start variable of G , we let S' be the start variable of G'.
Now the new CFG G' can generate the suffix of A , and hence context-free language is closed under the suffix operation.
If you know how to do Suffix, then you also know how to do Prefix. Explicitly, show how transform a context-free grammar for a language $L$ to a context-free grammar of its reverse $L^R = \{x^R : x \in L \}$, where $x^R$ is the word $x$ in reverse (for example, $(for)^R = rof$). Then use the fact that
$$ \mathit{Prefix}(L) = \mathit{Suffix}(L^R)^R. $$
If you unroll this definition, you will actually get a direct construction for Prefix.