# Find a CFG for the set of prefixes of a CFL [duplicate]

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.

1. 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.)
2. Whenever X' →YZ is a rule of G , we add two new rules,X' →Y' Z and X' → Z' .
3. for each variable in G , we add X' → X and X' → ε
4. 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.
• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Nov 5 '14 at 0:08
• I give a proof sketch here. – Raphael Nov 5 '14 at 17:12
• I encourage you to choose a more specific title for your question. "Theory of formal languages" is very broad. – D.W. Dec 5 '14 at 1:57

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.