R is a regular language over $\Sigma=\{0,1\}$
$Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$
I need to prove that Sub(R) is context free.

I know that the quotient of a context free language with a regular language is context free but I can't seem to continue for there..


1 Answer 1


Let $\phi(R) \subseteq 0^*$ result from $R$ by substituting $0$ for $1$. Alternatively, $\phi(R) = \{ 0^{|w|} : w \in R \}$. The previous description makes it clear that $\phi(R)$ is also regular. Now $$ \operatorname{Sub}(R) = \phi(R) \{ 0^j 1^j \}, $$ the concatenation of the regular language $\phi(R)$ and the context-free language $\{0^j 1^j\}$.


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.