| Summary: | We say that a language $L$ is \emph{constantly growing} if there is a
constant $c$ such that for every word $u\in L$ there is a word $v\in L$ with
$\vert u\vert<\vert v\vert\leq c+\vert u\vert$. We say that a language $L$ is
\emph{geometrically growing} if there is a constant $c$ such that for every
word $u\in L$ there is a word $v\in L$ with $\vert u\vert<\vert v\vert\leq
c\vert u\vert$. Given two infinite languages $L_1,L_2$, we say that $L_1$
\emph{dissects} $L_2$ if $\vert L_2\setminus L_1\vert=\infty$ and $\vert
L_1\cap L_2\vert=\infty$. In 2013, it was shown that for every constantly
growing language $L$ there is a regular language $R$ such that $R$ dissects
$L$.
In the current article we show how to dissect a geometrically growing
language by a homomorphic image of intersection of two context-free languages.
Consider three alphabets $\Gamma$, $\Sigma$, and $\Theta$ such that $\vert
\Sigma\vert=1$ and $\vert \Theta\vert=4$. We prove that there are context-free
languages $M_1,M_2\subseteq \Theta^*$, an erasing alphabetical homomorphism
$\pi:\Theta^*\rightarrow \Sigma^*$, and a nonerasing alphabetical homomorphism
$\varphi : \Gamma^*\rightarrow \Sigma^*$ such that: If $L\subseteq \Gamma^*$ is
a geometrically growing language then there is a regular language $R\subseteq
\Theta^*$ such that $\varphi^{-1}\left(\pi\left(R\cap M_1\cap
M_2\right)\right)$ dissects the language $L$.
|
|---|