Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
