In case $L$ is context free language. $L_1 \setminus L_2 = \{x\in \Sigma ^* : \exists y\in L_2$ s.t $xy\in L_1 \}$ when $L_2$ is regular, is a context free language, thus using $L_1 = L$ ,$L_2 = \Sigma ^*$ one conclude that prefix$(L)$ is context free. However I wish to build a grammar for prefix$(L)$. My attempt so far was as follow: $L$ has a Chomsky's normal form grammar, $(N,T,S,P)$ so I defined the grammar $(N\cup N' , T, S, P\cup P')$ when $N' = \{A' : A\in A\}$ ,$P' = P\cup \{A\rightarrow BC' : A\rightarrow BC \in P \} \cup \{A' \rightarrow t : t\in T, A\rightarrow t \in P\} \cup \{A' \rightarrow \varepsilon\} $ my idea was that the non-tagged terms will be fully producted as in the usual grammar and the tagged terms might product a terminal or an $\varepsilon$. Yet I didn't succeed to prove it's a correct grammar for prefix$(L)$.

  • 1
    $\begingroup$ I think you should not add new productions to $A$, but you should have $A' \to BC' |B' $ when $A\to BC$ in the original CFG. When, $A\to t$, you have $A'\to t|\epsilon$ (as you are already doing). The new starting symbol should be $S'$. I think you are on the right track, though. $\endgroup$
    – chi
    Sep 21, 2018 at 14:16
  • $\begingroup$ Do you have a question? I see only a series of declarative sentences. I suggest you try to prove your approach correct. Try a proof by induction. Is there some barrier that prevents you from completing that project? Are you stuck at some specific point? $\endgroup$
    – D.W.
    Sep 22, 2018 at 6:14
  • $\begingroup$ @D.W. I was stuck because I was missing some production rules which were suggested in the comment, I am still working on proving that the suggested production rules give the right answer. $\endgroup$ Sep 22, 2018 at 6:27
  • $\begingroup$ @Apass.Jack I'll try to write it down tomorrow, Thanks! $\endgroup$ Sep 28, 2018 at 18:03
  • $\begingroup$ Tomorrow has arrived=), hope it's correct. @Apass.Jack $\endgroup$ Sep 29, 2018 at 6:31

1 Answer 1


Let $G$ be a Chomsky's normal form grammar for $L$. So $G = (N,T,S,P)$ when $P\subseteq\{A\rightarrow BC , A\rightarrow a : A,B,C \in N , a\in T \}$. We will defined $G'$ as follows: $G'= (N\cup N'\cup \bar{S} ,T,\bar{S},P')$ when:

  • $N' = \{A' : A\in N\} $
  • $P' = P\cup\{\bar{S} \rightarrow S' | \varepsilon \} \cup \{A'\rightarrow BC'|B' : A\rightarrow BC \in P\} \cup \{A'\rightarrow a|\varepsilon : A \rightarrow a \in P\}$

Observation - let $A \in N$ we define $L(A) = \{w\in T^* : A\Rightarrow^{*}_G w \}$, So, in $G'$ , $A'\Rightarrow^{*}_{G'} w\in prefix(L(A))$.

  • proof, by induction over production steps:

    • $A'\rightarrow^1w\in T^* \Rightarrow w \in \{a,\varepsilon\}$ due to $P'$ definition. So in $G$ ,$A\rightarrow a$ thus $\{a,\varepsilon\} \in prefix(L(A))$.

    • assumption - $\forall A'\in N'$, $A'\Rightarrow^{k <n}w\in prefix(L(A)) $

    • $A'\Rightarrow^n w\in T^*$, so $A'\rightarrow^1 \gamma\Rightarrow^{n-1} w$, thus $\gamma \in \{BC' , B'\}$: In case $\gamma = B'$ then $B'\Rightarrow^{n-1} w\in prefix(L(B))$ and $A'\rightarrow B' \Rightarrow A\rightarrow BC \in P$ then $prefix(L(B)) \subseteq prefix(L(A))$. If $\gamma = BC'$, $B$ products $w_1 \in prefix(L(A))$ because $A\rightarrow BC \in P$, and $BC \Rightarrow^* w_1w_2\in L$ when $B \Rightarrow^* w_1 , C\Rightarrow^*w_2$, and $C'$ products $w_{2}' \in prefix(L(B))$ from the assumption. Thus $A' \Rightarrow w_1w_2'$ which is a prefix of $w_1w_2 \in L(A)$.

$L(G') \subseteq prefix(L)$:

  • $\bar{S} \rightarrow^1 \varepsilon$ , $\varepsilon \in prefix(L)$.

  • $\bar{S} \Rightarrow ^n w\in T^* \setminus \{\varepsilon\}$ , so $\bar{S}\rightarrow S'\Rightarrow ^{n-1}w$ now, using the first observation we made $S' \Rightarrow^* w\in prefix(S) = prefix(L)$.

    So $\bar{S} \Rightarrow^* w\in T^*$ means $w\in prefix(L)$.

$prefix(L) \subseteq L(G')$:

Observation : in case $A\Rightarrow^* w\in T^*$, then $A' \Rightarrow^* w' \in prefix(w)$ for all $w'\in prefix(w)$.

proof by induction over $w$'s length:

  • $A\rightarrow a$ $\Rightarrow$ $A' \rightarrow a$ and $A'\rightarrow \varepsilon$, due to $P'$ definition, when $prefix(a) = \{a,\varepsilon\}$.
  • $A\Rightarrow^* w, |w|=n$, so $A\rightarrow BC \Rightarrow^* w_1w_2 =w$ when $B \Rightarrow^* w_1 ,C \Rightarrow^* w_2$ (from $P$'s definition in chomsky's form). For $w'\in prefix(w)$:

    • in case $w' \in prefix(w_1)$, then $B'\Rightarrow^* w'$ from the induction assumption ($|w'|<n$, and the assumption stands for every $A'\in N'$ ). So $A'\rightarrow B' \Rightarrow^* w'$ as wanted.

    • in case $w' = w_1w_2'$ when $w_2'\in prefix(w_2)$ the same arguments holds for $c' \Rightarrow^* w_2'$, thus $A'\rightarrow BC' \Rightarrow^*w_1w_2'$.

For $w \in prefix(L)$:

  • in case $w = \varepsilon $ , $\bar{S} \rightarrow \varepsilon$.

  • otherwise $\exists z\in T^*$ such that $wz \in L$, so $S\Rightarrow_G^{*} wz$ and by the observation we made $S'\Rightarrow^* w'\in prefix(wz)$ for all $w'\in prefix(wz)$ and particularly $w$ it self. So $\bar{S} \rightarrow S'\Rightarrow ^* w$. Thus $w\in L(G)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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