# $L$ is a context free language so prefix$(L)$ is also context free language

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)$$.

• 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. – chi Sep 21 '18 at 14:16
• 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? – D.W. Sep 22 '18 at 6:14
• @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. – dan Sep 22 '18 at 6:27
• @Apass.Jack I'll try to write it down tomorrow, Thanks! – dan Sep 28 '18 at 18:03
• Tomorrow has arrived=), hope it's correct. @Apass.Jack – dan Sep 29 '18 at 6:31

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

• $$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'|, 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)$$

• Typo one, "$P=\{A\rightarrow BC , A\rightarrow a : A,B,C \in N , a\in T \}$" should be "$P\subseteq\{A\rightarrow BC , A\rightarrow a : A,B,C \in N , a\in T \}$". Typo two, "$prefix(L) \subseteq L(G)$" should be "$prefix(L) \subseteq L(G')$". – Apass.Jack Sep 30 '18 at 5:14