Let $G$ be a <PERSON>'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. 532
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 <PERSON>'s form). 677