# Adherence of languages and the Dyck language

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)$.
• yes, it isn't $D = (D_s)^*$. Jan 5, 2014 at 11:12