Prove or disprove
Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
Prove or disprove
Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $ L \cap R $ and $L \cap \overline{R} $ are infinite and regular.
Copyright © 2021 JogjaFile Inc.
As stated, this cannot be true. If $L \cap R$ and $L \cap \overline{R}$ are regular, then $L$ also must be regular as a sum of regular languages.
Here is a hint to show existence of $R$ such that $L \cap R$ and $L \cap \overline{R}$ are infinite. First, solve the problem when the alphabet is unary. You might use the fact that context-free languages for unary alphabets are regular. How does an infinite regular language for unary alphabet look like? For general alphabets, think about reduction to unary case (by substituting all letters to a single fixed one).