1
$\begingroup$

Is there a non-context free language A over the alphabet $\{0,1\}$ such that $A1 := \{a1 : a\in A\}$ is context free?

I was thinking of the language $A = \{0^n 1^{n-1} : n > 0\}.$ Unfortunately, this language is context-free. I’m not sure if one might be able to show that context-free languages are closed under the operation of removing the last bit from every such nonempty string.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

No. Note that $A = A1 / \{1\}$, the right quotient of $A1$ over $\{1\}$. Since $\{1\}$ is a regular language, we know that $A$ is context-free when $A1$ is context-free, thanks to this post that shows the right quotient of a context-free language over a regular language is also context-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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