1
$\begingroup$

The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \} $$ What about the context-free languages?

$\endgroup$
1
1
$\begingroup$

Let $L = \{a^nb^na^mbba^{3m} : n,m \geq 1 \}$, which is clearly context-free. Then $$ \operatorname{half}(L) \cap a^+b^+a^+b = \{ a^nb^na^nb : n \geq 1\}, $$ which is not context-free. Hence $\operatorname{half}(L)$ is not context-free.

(If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.