Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of infinite words such that $$ \mbox{Adh}(L) = \{ \xi \in X^{\omega} : A(\xi) \subseteq A(L) \} $$ i.e. the set of infinite words all of whose prefixes are prefixes of some words from $L$. Also write $u \le v$ if $u$ is a prefix of $v$. Define the Dyck language as $$ D = \{ v \in X^* : |v|_a = |v|_b \mbox{ and } \forall w \le v : |w|_a \ge |w|_b \}. $$ Examples of words from $D$ are: $ab, abaabb, aabbab$. Then it is claimed that $$ \mbox{Adh}(D) = \{ \xi \in X^{\omega} : \forall v < \xi : |v|_a \ge |v|_b \}. $$ Note that if this holds then $aaba^{\omega}$ should be in $\mbox{Adh}(D)$. I wanted to proof that claim, therefore I use the property of Adh: $$ \mbox{Adh}(L^*) = L^* \cdot Adh(L) \cup L^{\omega}. $$ And define a "strict" Dyck-language $D_s := \{ a^nb^n : n \ge 0 \}$, then $D = (D_s)^*$. It is $$ \mbox{Adh}(D_s) = \{ a^{\omega} \} $$ because $A(D_s) = \{ \varepsilon, a, ab, aa, aab, aabb, \ldots \} = \{ a^i b^j : i \ge j \}$ and just the subset $a^*$ fulfills the property that there exists an infinite word $\xi$ with $A(\xi) = a^*$, for $a^ib^j$ with $j > 0, i \ge j$ just has a finite number of completions $w$ such that $a^ib^jw \in A(D_s)$ (namely by $w = \varepsilon, b, bb, \ldots, b^{i-j}$) and so could not be the set of prefixes of some infinite word (the set $A(\xi)$ for infinite $\xi$ has two properties, 1) it is infinite and 2) the words could be lineary ordered according to the prefix relation, by 2) it is enough to look at some $a^ib^j$ and see of what words from $A(D_s)$ it is a prefix of).

Now using the property it is $$ \mbox{Adh}(D) = \mbox{Adh}(D_s^*) = D_s^* \cdot Adh(D_s) \cup D_s^{\omega} = D_s^* a^{\omega} \cup D_s^{\omega}. $$ But the word $aaba^{\omega}$ is not an element of this language, contradicting the first claim? Might the claim be false, or is there some flaw with my proof, I don't see it, maybe you can help?

PS: The claim (unproved) as well as the properties of the Adh-Operator is from the famous and often cited paper Adherences of Languages, which introduces those notions, so I think the claim is correct.


For each $n \geq 0$, the word $aaba^nb^{n+1}$ is in $D$, therefore $aaba^\omega$ is in $Adh(D)$.

| cite | improve this answer | |
  • $\begingroup$ yes, it isn't $D = (D_s)^*$. $\endgroup$ – StefanH Jan 5 '14 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.