1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Have you discovered anything? $\endgroup$
    – Chaos
    Sep 8, 2023 at 9:41

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

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.