Does this really define a 0L-system?

Question

Looking through old exams I found a problem stated as the following:

Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^* \to \Sigma^*$ is a homomorphism and $w \in \Sigma^*$ is a starting word. Furthermore define $L(S) = \{w,h(w),h(h(w)),...\}$ and define $L$ as a 0L-language if there exists a 0L-system $S$ such that $L$ = $L(S)$.

Prove or disprove that every 0L-language is context-free.

My solution looked like this:

Let $S_C = \{\{a\},a,h\}$ with $h(a)=aa$. Then $L(S_C)= \left\{ a^{2^n} \mid n \in \mathbb{N} \right\}$. Assume that $L(S_C)$ is context-free. Consider $z = a^{2^n} \in L(S_C)$. Since $|z| = 2^n > n$, by the pumping lemma for CFLs, $z=uvwxy$ such that $|vx| > 0$ and $|vwx| \leq n$. Consider $uv^2wx^2y = a^{2^n + i}$, where $0 < i \leq n$. We have $$2^n < |uv^2wx^2y| = 2^n+i \leq 2^n+n < 2^{n+1}$$ which holds true for all $n \in \mathbb{N}$. So $uv^2wx^2y \notin L(S_C)$ and therefore, $L(S_C)$ is not context-free and as such, not every 0L-language is context-free.

However, looking on the internet I found that all 0L-languages are, in fact, context-free, although they were defined a bit differently. I am relatively sure that my proof is correct, so the given definition for 0L-languages (or 0L-systems) above must be wrong, but I simply wanted to ask to make sure I wasn't missing something obvious.

Answer 1

I agree with you, the definition is incorrect. You are trying to prove that $\exists l.\text{0L-L(l)}\land\lnot CFL(l)$. This proof amounts at telling what $l$ is, to show (in separate branches) that it satisfies $\text{0L-L}(\cdot)$ and fails to satisfy $CFL(\cdot)$.

You pointed out $L(S_C)$ satifies $\text{0L-L}$ because $S_C$ exists and trivially complies to the definition of $L\text{-}System$ you provided.

The second branch instead requires to you disprove $l$ to be a CFL and you planned to do so by the pumping lemma.

I agree about the definition being incorrect because $L\text{-}Systems$ are defined as triples but $0L\text{-}Systems$ are characterized by productions whose LHS contains exactly one non-terminal symbol. The definition of $h:\Sigma^*\rightarrow\Sigma^*$ you provided does nothing to prevent the choice of a rewrite system that generates $L=\{a^nb^nc^n|n\in\mathbb{N}\}$ that is notoriously not a CFL.