1
$\begingroup$

This question already has an answer here:

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

marked as duplicate by D.W., Luke Mathieson, A.Schulz, Juho, David Richerby Dec 5 '14 at 8:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ 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. $\endgroup$ – FrankW Nov 5 '14 at 0:08
  • $\begingroup$ I give a proof sketch here. $\endgroup$ – Raphael Nov 5 '14 at 17:12
  • 1
    $\begingroup$ I encourage you to choose a more specific title for your question. "Theory of formal languages" is very broad. $\endgroup$ – D.W. Dec 5 '14 at 1:57
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.