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

CC BY-SA 3.0
2014-01-05T11:12:21.150Z
yes, it isn't $D = (D_s)^*$.
StefanH
CC BY-SA 3.0
2014-01-05T10:01:21.807Z
2014-01-05T10:01:21.807Z
J.-E. Pin
<p>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 &lt; \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 &gt; 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).</p>

<p>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?</p>

<p>PS: The claim (unproved) as well as the properties of the Adh-Operator is from the famous and often cited paper <a href="http://www.sciencedirect.com/science/article/pii/0022000080900100" rel="nofollow">Adherences of Languages</a>, which introduces those notions, so I think the claim is correct.</p>

<fl.formal-languages><automata-theory><topology><omega-language>
Adherence of languages and the Dyck language
StefanH
# Adherence of languages and the Dyck language

(Asked by: username_0 on 2014-01-04)

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](http://www.sciencedirect.com/science/article/pii/0022000080900100), which introduces those notions, so I think the claim is correct.

**Tags:** fl.formal-languages, automata-theory, topology, omega-language

---

## 1 answers

### Answer by username_1 on 2014-01-05. Score: 5 | Accepted answer

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

> **Comments:**
> **username_0**: yes, it isn't $D = (D_s)^*$.  

---

