patternMinor
Does the following transformation preserve context-freeness?
Viewed 0 times
thepreservefollowingdoescontexttransformationfreeness
Problem
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-free?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?
My guess is that it will preserve context-freeness. Can anyone provide an elementary proof of this?
Solution
Counter-example:
$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$
$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$
$L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free.
Any nonempty word $x \in L^\#$ has a prefix $p = a^n b^n c^m \in L_1$. It must be $n = m$, because due to $L_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:
$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$, which is not context-free.
$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$
$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$
$L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free.
Any nonempty word $x \in L^\#$ has a prefix $p = a^n b^n c^m \in L_1$. It must be $n = m$, because due to $L_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:
$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$, which is not context-free.
Context
StackExchange Computer Science Q#10183, answer score: 5
Revisions (0)
No revisions yet.