Is L' context free language?

Question

Given context free grammar : G=(V,T,P,S).

and L'={a $\in$ (V $\cup$T)* | S$\Rightarrow$*a} when $\Sigma$=V $\cup$ T

Is L' context free language ?

I think no because for the grammer:

G=(S,{a,b},P,S) ,P={ S$\rightarrow$aSb|ab}

we will get that L' is:

L'={$a^nS^nb^n$}$\cup${$a^nb^n$} and L' is not context free language.

Answer 1

Given context-free grammar $G = (V, T, P, S)$, define $G' = (V, T \cup V', P \cup P', S)$, such that $V'$ has one element for each element of $V$,

$$ V' = \{ v' \mid v \in V \} \enspace, $$

and, for each element $v \in V$, $P'$ contains the production $v \rightarrow v'$. The language of $G'$ is context-free, and is isomorphic to $L'$.

Answer 2

Your initial definition: $$ L'= \{a \in (V \cup T)^* \mid S \Rightarrow^* a \} \quad \text{when } \Sigma =V \cup T \quad (*) $$ seems to use $V$ as set of non-terminals and $T$ as set of terminals. $L'$ consists of all words $a \in \Sigma^*$ which can be produced via $P$ from the start symbol $S\in V$ in finite many steps.

The language generated from $G=(V, T, P, S)$ is $$ L(G) = \{ a \in T^* \mid S \Rightarrow^* a \} \quad (**) $$ To have $L'$ be context-free, one has to provide a context-free grammar $G'=(V', T', P', S')$ which generates it similar to $(**)$.

Solution:

We have $T' = V \cup T$ from the definition of $L'$ and comparison to $(**)$.

The requirement $\emptyset = V' \cap T'$ needs us to come up with a $V'$ disjoint with $V$. As $S \in V$, $S' \in V'$ this means $S' \ne S$.

$P$ contains the production rules $\alpha_i \to \beta_i$ with $\alpha_i \in V$ and $\beta_i \in (V \cup T)^*$.

If $a \in L'$ then $a \in (V\cup T)^*$ and we have $S = u_1 \Rightarrow \dotsb \Rightarrow u_k = a$ for $k \ge 1, k\in \mathbb{N}$, $u_i \in (V\cup T)^*$ because the productions from $P$ are used:

$u \Rightarrow v$ means there is a production rule $\alpha \to \beta$ and prefix $p$, suffix $s$ such that $u = p \alpha s$ and $v = p \beta s$.

We now choose some set $V'$ disjoint with $V$ but with the same number of elements, as $V$ is finite, this should always be possible. We choose some bijection $f$ between $V$ and $V'$: $$ v' = f(v) \quad (v \in V) $$ Then $V' = f(V)$, $S' = f(S)$.

For each production $\alpha \to \beta$ from $P$, we define a production $\alpha' \to \beta'$ for $P'$, where $\alpha' = f(\alpha)$ and $\beta'$ such that each symbol $s$ from $\beta$ with $s\in V$ is replaced by $s'=f(s)\in V'$, while the symbols $s\in T$ will be kept. A little bit sloppy, we write this as $\beta'=f(\beta)$.

This $G'$ so far will generate (in the sense of $(*)$) all words $a' = f(a)$ where $a\in L'$. These $a'$ might contain non-terminal symbols from $V'$, $a' \ne a$ might occur, so we add production rules $v' \to v = f^{-1}(v')$ for each $v' \in V$ to $P'$.

This should give $$ L' = L(G') $$ according to $(*)$.

Example:

$$ G = (V=\{S\}, T=\{a,b\}, P, S) $$ with production rules $P$: $$ S\to aSa \mid bSb \mid \varepsilon $$ Then $$ L' = \{ wSw^R \mid w \in T^* \} \cup \{ ww^R \mid w \in T^* \} $$ Then $$ G' = (V'=\{ S' \}, T'=\{ S, a, b \}, P', S) $$ with $P'$: $$ S' \to aS'a \mid bS'b \mid \varepsilon \mid S $$ The first three productions will generate (in the sense of $(*)$) $$ f(L') = \{ wS'w^R \mid w \in T^* \} \cup \{ ww^R \mid w \in T^* \} $$ the last one extends to $$ \{ wS'w^R \mid w \in T^* \} \cup \{ wSw^R \mid w \in T^* \} \cup \{ ww^R \mid w \in T^* \} $$ however generated in the sense of $(**)$, thus restricted to $T'=\{ S, a, b \}$ we get $L'$.