# Does this really define a 0L-system?

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.

• Have you discovered anything? Sep 8, 2023 at 9:41

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.