patternMinor
$L$ is a context free language so prefix$(L)$ is also a context free language
Viewed 0 times
prefixfreelanguagealsocontext
Problem
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)$.
Solution
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:
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^ 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'|
-
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)$
- $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'|
-
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)$
Context
StackExchange Computer Science Q#97613, answer score: 2
Revisions (0)
No revisions yet.