数理解析研究所講究録 1222 巻 2001 年 114-122

114
The measure of an omega regular language isrational
Takeuti Izumi (竹内 泉)
Graduate School of Informatics, Kyoto Univ. 606-8501, JAPAN,
takeut i@kuis.kyoto-u.ac.jp

Abstract. An omega regular language is the omega language which isrecognised by aBuchi automaton. It has been known that the measure ofan omega regular language recognised by adeterministic Buchi automaton
is arational number. This paper shows the measure of every omega regular
language is arational number.

1Introduction
An omega regular language is the omega language which is recognised by aBuchi
automaton. Many studies on omega regular languages and Buchi automata appear
in the literatures [Staiger97, Thomas], which contain the proofs of most propositionsin Sections 2of this paper. An important property is that the recognising power of
non-deterministic Buchi automata is properly stronger than that of deterministic Buchi
automata.
Yen Hsu-Chun and Lin Yih-Kai showed that the measure of an omega regular language recognised by adeterministic Buchi automaton is arational number [Lin&Yen].
Unfortunately, their method cannot be applied to non-deterministic Buchi automata.
Therefore, the characterisation on the general omega regular language has remained
open.
The main result of this paper is that the measure of every omega regular language
is arational number. In order to prove this theorem, we
use two notions, which
are irreducibility and sparseness. The definition of irreducibility is the following: anomega regular language
is irreducible iff for each word
there is aword$x\in X$ for any
such that $x\in X$ iff. The definition of sparseness isthe following: an omega regular language $X$ is sparse iff for each word
there is awordsuch thatfor any. The notion of irreducibility is not
new at this paper. Staiger called irreducible sets strongly connected in the literature[Staiger83]. The purpose of these two notions is to show the detachment lemma (3.13).
The detachment lemma states that an omega regular language can be divided into
asparse set and some other subsets each of which is the concatenation of aregular
language and an irreducible set. We will show some other lemmata on the measures.
Lemma 4.13 states that the measure of an irreducible set is 1or 0. Lemma 4.14 statesthat the measure of asparse set is 0. These three lemmata are crucial. And then,we will show the lemma such that the measure of each finite state set is arational
number. The main lemma is proved with these lemmata above and the theorem by$\mathrm{w}\mathrm{i}\mathrm{U}$$X\subset\Sigma^{w}$$w\in\Sigma^{*}$$v\cdot$$w\cdot$$v\in\Sigma^{*}$$x\in\Sigma^{w}$$v\in\Sigma^{*}$$w\in\Sigma^{*}$$v\cdot$$w\cdot$$x\not\in X$$x\in\Sigma^{w}$

115
Lin and Yen. Our main result.is an immediate consequence of this main lemma, for
an omega regular language is finite-state.

2Buchi Automaton
Definition 2.1 (Buchi Automaton) ABuchi automaton is defined by five comp0nents $(\Sigma, S,T,s_{0},F)$ , where each component has the following meaning:$\Sigma$$S$$T\subset S\mathrm{x}\Sigma\cross S$$s_{0}\in S$$F$:alphabet, the set of symbols:the set of states: transition relation:the initial state:the set of final states

Actually, final states are not final, but are to be visited infinitely many times. We callthem final states only because of the traditional reason.
Let $B$ be aBuchi automaton such as $B=(\Sigma, S,T, s_{0},F)$ . Then $L(B)$ is asubset,
iff thereofwhich defined as the following. For
for each $i=1,2$ , , and that there aresuch thatis. We say that the Buchi automaton $B$ recognises
such that
infinitely many
the set $L(B)$$(\sigma_{1}, \sigma_{2}, \ldots)\in\Sigma^{\omega}$$\Sigma^{\omega}$$(s_{1}, s_{2}, \ldots)\in S^{\omega}$$i’ \mathrm{s}$$(\sigma_{1}, \sigma_{2}, \ldots)\in L(B)$$(s_{*-1}.,\sigma.\cdot, s:)\in T$$\ldots$$\mathrm{S}:\in F$

Definition 2.2 (Regularity) Aset X
automaton B.

$\subset\Sigma^{\omega}$is regular iff X $=L(B)$ for some Buchi

is called an omega language, and aregular subset of
Notation 2.3 Asubset ofis called an omega regular language. We sometimes call aomega language aset inthis paper. Thus, an omega regular language is called aregular set. Note that what iscalled aset not always an omega language.
$\Sigma^{w}$$\Sigma^{\omega}$a language. We use the notion of regular languages
Remark 2.4 We call a subset ofdefinition,with ordinal finite automata.
isdefinedwhich
as the ordinal$\Sigma^{*}$

Proposition 2.5 (Buchi ’60) A regular set is an$\mathrm{F}\mathrm{a}\mathrm{S}$-set.

Proof. By Buchi [Biichi], or also by Remark 3.4 on Page 354 in the literature[Staiger97].
I
is a regular language. Then $W$ . ? is recognised by
Proposition 2.6 If
deterministic Buchi automaton.
$W\subset\Sigma^{*}$$a$

Proof. By Proposition 3.4 on Page 355 with Theorem 3.1 on Page 354 in the literature[Staiger97].
I116
Notation 2.7 For 1J|\ldots ) E , we write tp .z or) or,.
{rp .z |zE }. For sets W$\ovalbox{\tt\small REJECT}$\ldots ,\ldots ,$w_{m\rangle}x_{1},$$\ovalbox{\tt\small REJECT} \mathrm{w}\mathrm{z}$’$\ovalbox{\tt\small REJECT}$$(\mathrm{z}_{1},\mathrm{z}_{2},$$\ovalbox{\tt\small REJECT}$$\mathrm{c}E^{\ovalbox{\tt\small REJECT}}$$\mathrm{t}\mathrm{t}\mathrm{r},\mathrm{z}_{1}\ovalbox{\tt\small REJECT}" r\ovalbox{\tt\small REJECT}_{2},$$(^{\ovalbox{\tt\small REJECT}}eu_{\mathit{1}},$\ldots ,$\ldots \mathrm{r}\ovalbox{\tt\small REJECT}.$\ldots ,r.)EE’ or X
and xof 117 and $ which isconcatenation
the
for
,
\ldots ). For aword wEZ’and aset X.
”and CI”, W.
}.
|
{t0

$15|7_{m})\mathrm{E}\mathrm{Z}$$\ovalbox{\tt\small REJECT}$$(\mathrm{z}_{1},\mathrm{z}_{2},$$(1\mathrm{J})_{)}$$(\mathrm{j}1|7),1^{\mathrm{j}\mathrm{j}}2,$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$\mathrm{C}2^{\ovalbox{\tt\small REJECT}}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$\mathrm{t}\mathrm{t}^{\mathrm{r}}$Definition 2.8 (States) For$w\cdot x\in X\}$ , and $S(X)$ forof $X$ .

and$X\subset\Sigma^{w}$$w\in\Sigma^{*}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}^{\ovalbox{\tt\small REJECT}}$$\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$\mathrm{t}\mathrm{t}^{\mathrm{r}}\mathrm{E}$, we write $X/w$ for $\{x\in\Sigma^{uJ}|$. We call aset in $S(X)$ States$\{\mathrm{Y}\subset\Sigma^{w}|w\in\Sigma^{*},\mathrm{Y}=X/w\}$

Remk 2.9 $(X-\mathrm{Y})/w=X/w-\mathrm{Y}/w$
Definition 2.10 (Finite-state sets) Aset

$X\subset$?is finite-state iff $S(X)$ is finite.

Proposition 2.11 Each regular set is finite-state.

1

Proof. In [Thomas].
Proposition 2.12 For a finite-state set $X$$\{w\in\Sigma^{*}|X/w=\mathrm{Y}\}$ is a regular language.

$\subset p$

and a set$\mathrm{Y}\subset?$,$\theta\iota e$

set of words
1

Proof. Easy.

3Irreducible set
Definition 3.1$(\mathrm{A}\mathrm{c}\mathrm{c}\mathrm{a}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{b}\underline{1}\mathrm{t}\mathrm{y})$For$X,\mathrm{Y}\in\Sigma^{\rho}$, the relation$S(X)$ , that is, there is $w\in\Sigma^{*}$ such that $\mathrm{Y}=X/w$. This$Xarrow \mathrm{Y}*$$arrow*$$\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\dot{\mathrm{i}}\mathrm{o}\mathrm{n}$holds iff$\mathrm{Y}\in$

is called accessi-

bility.

Remark 3.2$\mathrm{A}\mathrm{c}\mathrm{c}\infty \mathrm{i}\mathrm{b}\underline{\mathrm{i}\mathrm{l}\mathrm{i}}\mathrm{t}\mathrm{y}$is reflexive and transitive.

a preo rder over
Proposition 3.3 Let $D$ be a non-empty finite set, and a relation$D$ , that is, areflexive transitive relation. Then, there is a maximal element with respect
to the preorder .
$\leq be$$\leq$

Proof. Induction on the number of the elements ofDefinition 3.4 (Irreducibility) A
for each$\underline{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}}\mathrm{t}\triangleright \mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{e}$

$D$

.

.

set $X\in\Sigma$ is irreducible iffI$\mathrm{Y}\prec X*$$\mathrm{Y}\in S(X)$

Remk 3.5 Irreducible sets are called strongly connected in the literature [Staiger83].
Proposition 3.6 For a finite-state set
set in $S(X)$ .

$X\subset\Sigma^{\omega}$, there exists at least one irreducible

117
$*$

Proof. An irreducible set is amaximal element with respect to , and the domain
I$S(X)$ is non-empty and finite. Hence, it exists by Proposition 3.3.
$\ovalbox{\tt\small REJECT}$Definition 3.7 (Sparseness) Afinite state set $X$ is sparse iff iff$\mathrm{Y}arrow*\emptyset$

for each$\mathrm{Y}\in S(X)$

Proposition 3.8 If

Proof. We haveirreducible. Thus

$X\in\Sigma^{\omega}$$\mathrm{Y}arrow\emptyset*$$\mathrm{Y}=\emptyset$.

is sparse and $\mathrm{Y}\in S(X)$ is irreducible, thenby the definition of spaeseness. Hence (1)Definition 3.9 ( -operation)For sets X,Y$*$$X*\mathrm{Y}=\{w$.x $\in X$ |$\exists v\in\Sigma^{*}.$$\subset\Sigma^{w}$, the set$arrow \mathrm{Y}*$$X*\mathrm{Y}\in\Sigma^{\omega}$$\mathrm{Y}=\emptyset$.

because$\mathrm{Y}$is1
is defined as:

x $\in X/w=\mathrm{Y}/v\}=\cup\{w$ . $(X/w)|X/w\in S(\mathrm{Y})\}$ .

. Put $W=\{w\in\Sigma^{*}|X/w\in S(\mathrm{Y})\}$ .
Remark 3.10 Let $X$ and be subsets of$V\subset
W$such that for each $w\in W$ there are $v\in V$
Then, there is aprefix-free subset$(X/v)$ for this $V$ .
such that $v\cdot u=w$ . It holds that
and$\Sigma^{\omega}$$\mathrm{Y}$$u\in\Sigma^{*}$$X* \cdot \mathrm{Y}=\bigcup_{v\in V}v\cdot$

Remark 3.11 In general, for eachthat for each $w\in W$ there are $v\in V$ andlanguage, then so is .

$W\subset\Sigma^{*}$

there is aprefix-free subset $V\subset W$ such
such that $u=w$ . If $W$ is aregular$u\in\Sigma^{*}$$v\cdot$$V$

Proposition 3.12 For sets

Proof. For$x\in\Sigma^{w}$$X,\mathrm{Y}\in\Sigma^{w}$

and a word

$w\in\Sigma^{*}$, $(X/w)*\mathrm{Y}=(X*\mathrm{Y})/w$ .

, $x\in(X*\mathrm{Y})/w$ iff $wx\in X*\mathrm{Y}$ , which is equivalent to$\exists u,v\in\Sigma^{*}.\exists y\in\Sigma^{w}$. $wx=uy\ y\in X/u=\mathrm{Y}/v$ .

This is equivalent to$\exists u,u’$or$\exists u$,$v\in\Sigma^{*}.\exists y\in\Sigma^{\omega}$. $u=wu’$ $\ x=u’y\ y\in X/wu’=\mathrm{Y}/v$, $w’$ , $v\in\Sigma^{*}.\exists y\in\Psi$ . $w=uvl\mathit{9}\tau dx$$=y\mathit{8}c$$y\in X/u=\mathrm{Y}/v$... (1)... (2)

By deleting the variable , the upper case (1) is transformed into the equivalent fomula:. $x=u’y\ y\in X/wu’=\mathrm{Y}/v$ .
,$u$$\exists u’$$v\in\Sigma^{*}.\exists y\in\Sigma^{w}$

We consider the lower case (2). Suppose that$w=uw’$ $\ ulx=y\ y\in X/u=\mathrm{Y}/v$.

Then$x\in X/uuf$ $=X/w=\mathrm{Y}/vvf$.

This implies$\exists u’,d$$\in\Sigma^{*}.\exists\oint\in\Sigma^{\omega}$. $x=u’ \oint\ \phi$ $\in X/wu’=\mathrm{Y}/v’$ .

118
by instantiatingcase (2) implies$u’$with empty word,$\exists u’,\sqrt\in\Sigma^{*}.\exists f\in B^{\theta}$$\sqrt$with $vu’.$’and

$\nu$

with

. $x=u’y$ &y\in X/wu’$x$. Therefore, the lower$=\mathrm{Y}/\tau f$.

In the formula with disjunction, the right part of disjunction implies the left part.
Hence, the whole formula is equivalent to the left part. Thus it is equivalent to:$\exists u,v\in\Sigma^{*}.\exists y\in?$. x=uy&y\in X/wu$=\mathrm{Y}/v$.

This is equivalent to$\exists u,v\in\Sigma^{*}.\exists y\in\Sigma.$.x=uy&y\in (X/w)/u$=\mathrm{Y}/v$.

This is equivalent to $x\in(X/w)*\mathrm{Y}$ .

1

Lemma 3.13 (Detachment lemma) For each finite-state set $X$ , there are a sparse
set , a finite index set I and indexed familiesand {Y. } such that
$Z$$\{W_{}\}:\in I$$X=Z \cup\bigcup_{:\epsilon I}W_{\dot{1}}$.

$\cdot$$\mathrm{Y}_{j}=\emptyset$$Z\cap W_{j}\cdot$$:\in I$$\mathrm{Y}_{\dot{1}}$where each W. is a prefix-free regular language, each
andfor any $i\neq j$ .

$\mathrm{Y}_{}\cap W_{\mathrm{j}}\cdot$$\cdot$$\mathrm{Y}_{}$

is an irreducible set, and. .

$W_{*}$$\mathrm{Y}_{j}=\emptyset$

Proof. The proof is done by induction on the number of the elements of $S(X)-\{\emptyset\}$ .
(Base case) If $S(X)-\{\emptyset\}=\emptyset$ , thenand the assertion of this lemma holds.
$X$(Induction step) We show that the case of can be reduced to the case of another$X’$ where $S(X’)-\{\emptyset\}$ has less elements than $S(X)-\{\emptyset\}$ .
By the Proposition 3.6, there is at least one irreducible set in $S(X)$ . If the only
irreducible set in $S(X)$ is the empty set, then $X$ is sparse, and the assertion of thelemma holds. Therefore we assume that there are non-empty irreducible set.
Put
as such an irreducible set. Eachis dso irreducible by thedefinition of irreducibilty.
If $S(X)=S(\mathrm{Y})$ , then $X$ is already ineducible, and the assertion of the lemma$X$ where 0is sparse and the set
holds, because
is the singleton of
empty words, which is aregular language. Therefore, we assume that $S(X)\neq S(\mathrm{Y})$ ,.
that is,First we will show thatcan be decomposed as
and it$X=\emptyset$$\mathrm{Y}\in S(X)$$\mathrm{Y}\in S(X)$$Z\in S(\mathrm{Y})$$X=\emptyset\cup\{()\}\cdot$$\{()\}$$X\not\in S(\mathrm{Y})$$X*\mathrm{Y}$$\mathrm{Y}_{}$$X* \mathrm{Y}=\bigcup_{:\epsilon t}W_{}\cdot$

holds that for each $:\in I$ the set
is aprefix-free regular language, and.
has, andLet I be aindex set which has the same number of elements as. Put V4 $=\{v\in\Sigma^{*}|X/v=\mathrm{Y}_{\dot{1}}\}$ . Then $X*\mathrm{Y}=$be equal to$(X/v)$ . As Remark 3.10, there is aprefix-free subset$W_{\dot{1}}$$\mathrm{Y}_{}\in S(\mathrm{Y})$$S(\mathrm{Y})$$\{\mathrm{Y}_{\dot{1}}|i\in I\}$

$S(\mathrm{Y})$$W \subset\bigcup_{:\in I}V.\cdot$$\bigcup_{:\in I}V_{}\cdot \mathrm{Y}_{}=\bigcup_{:\in Iv}\bigcup_{\in V_{l}}v\cdot$

such that$X* \mathrm{Y}=\bigcup_{w\in W}w\cdot$$(X/w)$As Proposition 2.12, each

$V\dot{.}$. Put$W_{\dot{1}}$$=W\cap V_{\dot{1}}$. Then$W_{}$

is prefix-free.

is aregular language, then so is$\bigcup_{:\in t}V_{}$, because I isfinite. As Remark 3.11, the subset $W$ is aregular language, and then so is$W_{}$.

119
Therefore we have

$X* \mathrm{Y}=.\bigcup_{\in I}W_{}\cdot \mathrm{Y}_{}$

where for each$\in I$,$W_{}$

is prefix-free regular. Moreover, each and are disjoint for $:\neq j$ . Therefore
language andeachandare disjoint. In addition,is prefix-free. These facts imply
that each W.
andare disjoint.
$X-X*\mathrm{Y}$.
Next we discuss$Z|arrow
Z-Z*\mathrm{Y}$The mapping
is function
into $S(X-X*\mathrm{Y})$ . That is because
if $Z\in S(X)$ then $Z=X/w$ for some . Hence $Z*\mathrm{Y}=(X*\mathrm{Y})/w$ by Proposition
3.12, so $Z-Z*\mathrm{Y}=X/w-(X*\mathrm{Y})/w=(X-X*\mathrm{Y})/w\in S(X-X*\mathrm{Y})$. Moreover,the mapping $Z\vdash*Z-Z*\mathrm{Y}$ is asurjection. That is because if $Z’\in S(X-X*\mathrm{Y})$ thenfor some , it holds that $Z’=(X-X*\mathrm{Y})/w=(X/w)-(X/w)*\mathrm{Y}$ and $X/w\in S(X)$ .
, and of cause
Note that this mapping maps into.
$S(X-X*\mathrm{Y})-\{\emptyset\}$Hence, the number of elements ofis less than or equal to that of, Therefore the number of elements of $S(X-X*\mathrm{Y})-\{\emptyset\}$ is less thanthat of $S(X)-\{\emptyset\}$ . Thus, induction hypothesis holds for $S(X-X*\mathrm{Y})$ .
By the induction hypothesis, there are asparse set
and familys
and.such that
where , $\{W_{*}’.\}=i\in I’$ and$V_{}$$\mathrm{Y}_{}\in S(\mathrm{Y})$$W_{}\cup W_{j}$$W_{j}$$W_{\dot{1}}$$\cdot$$V_{j}$$W_{j}\cdot$$\cdot \mathrm{Y}_{\dot{*}}$$\mathrm{Y}_{j}$$\mathrm{o}\mathrm{f}S(X)$

$w$

$w$

$\mathrm{Y}-\mathrm{Y}*\mathrm{Y}=\emptyset$$\mathrm{Y}$$\emptyset-\emptyset*\mathrm{Y}=\emptyset$$S(X)-\{\emptyset,\mathrm{Y}\}$$Z$$\{W’.\cdot\}:\epsilon I’$$Z$$\{\mathrm{Y}’\dot{.}\}_{*\in I’}$

$X-X* \mathrm{Y}=Z\cup\bigcup_{:\in P}W’.\cdot\cdot \mathrm{Y}_{}’$$\{\mathrm{Y}_{}’\}=i\in I’$satisfies the disjointness in the assertion of this lemma.
Therefore$X=X* \mathrm{Y}\cup(X-X*\mathrm{Y})=Z\cup(\bigcup_{:\in F}W_{*}’..\mathrm{Y}’.\cdot)\cup(\bigcup_{:\in I}W.\cdot\cdot \mathrm{Y}_{\dot{1}})$The disjointness in the assertion holds because$X*\mathrm{Y}$and $X-X*\mathrm{Y}$ are disjoint.

I

4Measure
Remark 4.1 We fix the alphabet$\Sigma$

Notation 4.2 We use the notations.
for$\Sigma^{\omega}$which consists of

$U$

$n$

and $U(w)$ such as

symbols.
$U=\Sigma^{w}$

and$U(w)=w\cdot\Sigma^{\omega}\subset$$w\in\Sigma^{*}$

Definition 4.3 (Measure) For aset

$X\subset\Sigma^{\omega}$, the measure $\mu(X)$ is defined as:$\mu(X)=\inf\{_{:\in I}\sum n^{-1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)}:|X\subset\bigcup_{:\in I}U(w.\cdot)\}$Definition 4.4 (Measurability) Aset.

$X\subset\Sigma^{w}$.

is measurable iff $\mu(X)+\mu(U-X)=$$1$

Remark 4.5 This $\mu(X)$ is usually called the outer measure if $X$ is not neasurable.
Remark 4.6 The following propositions 4.7 and 4.8 are easily seen form the discussion
in the literature [It\^o].

120
Proposition 4.7 If $X\subset U$ is$.aF\sigma\delta$-set, then $X$ is measurable.

Proposition 4.8 If ffie set of wor&{w:that.

$\in\Sigma^{*}||$$\in I$} is prefi-free, Then, it holds$\mu(_{:\epsilon t}\cup w:\cdot X_{)}=\sum_{:\in I}2^{-1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w:)}\mu(X.\cdot)$.

Lemma 4.9 A regular set is measurable.
Proof. By Propositions 2.5 and 4.7.

I

Theorem 4.10 (Lin &Yen ’00) For each deterministic Buchi automaton B, themeasure $\mu(L(B))$ is rational.
Proof. By Lin and Yen [Lin&Yen].

I

Remk 4.11 Lin and Yen proves the theorem above with the property of Markov
chains. Adeterministic Buchi automaton is regarded as aMarkov chain in their proof.
Unfortunately, their method cannot be applied to non-deterministic Buchi automata.

Lemma 4.12 $IfX$ is irreducible, then for each$\mathrm{Y}\in S(X)$, $\mu(X)=\mu(\mathrm{Y})$ .

Proof. Because $S(X)$ is finite, then there exists $m= \max\{\mu(\mathrm{Y})|\mathrm{Y}\in S(X)\}$ . Put$E=\{\mathrm{Y}\in S(X)|\mu(\mathrm{Y})=m\}$ . Then the assertion of this lemma is equivalent to$E=S(X)$ . We will prove this by reductio ad absurdum.
and $\mathrm{Y}’\in S(X)-E$ .
as
Suppose that $S(X)-E$ is not empty. Put and,Y2, ,
such
Because $X$ is irrducible, there is asequence of sets
, there is apair
and. Because
for some
that
$\in
E$
. Note that
andsuch that$\mathrm{Y}\in E$$\mathrm{Y}’$$\mathrm{Y}$$\mathrm{Y}_{l-1},\mathrm{Y}_{l}=\mathrm{Y}’$$\mathrm{Y}=\mathrm{Y}_{1}$$\ldots$$\sigma\dot{.}\in\Sigma$$\mathrm{Y}_{}/\sigma_{}=\mathrm{Y}_{+1}$$(\mathrm{Y}_{\dot{1}},\mathrm{Y}_{+1})$$\mathrm{Y}_{1}\in E$$\mathrm{Y}_{l}\not\in E$$\mathrm{Y}_{+1}\not\in E$$\mathrm{Y}_{\dot{1}}$Y4$= \bigcup_{\sigma\in B}\sigma\cdot(\mathrm{Y}_{}/\sigma)$.

By Proposition 4.8,$\mu(\mathrm{Y}.\cdot)=\frac{1}{n}\sum_{\sigma\in B}\mu(\mathrm{Y}_{}/\sigma)$

Therefore,$m \leq\frac{1}{n}\mu(\mathrm{Y}_{+1})+\frac{n-1}{n}m<\frac{1}{n}m+\frac{n-1}{n}m=m$,that is, $m<m$ . This is contradiction.

I

Lemma 4.13 For each irreducible set $X$ , $\mu(X)=1$ or $\mu(X)=0$ .
absurdum.
Proof. We will prove this theorem by reductio
Put $m=\mu(X)$ . If $m$ is neither 1nor 0, then there is such that $0<\epsilon<m(1-m)$ .
and that
As the definition of , there is aset $\{w:|:\in I\}$ such that$\mathrm{M}$$\epsilon$$\mu$$X \subset\bigcup_{:\in I}U(w:)$

121$m< \sum_{:\in I}n^{-1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)}‘<m+\epsilon$.

Without loss of generousity we can assume that $\{w.\cdot|i\in I\}$ is prefix-free.
Then, there is afinite subset
such that$J\subset I$$\frac{\epsilon}{1-m}<\sum_{j\in J}n^{-1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w_{f})}$Put$V= \bigcup_{j\in J}U(w_{j})$exists because$J$, $b=\mu(V)$ andis finite. Note.

$l= \max\{1\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w_{j})|j\in J\}$$b> \frac{\epsilon}{1-m}$

. Let

$K$

. The number$l$be the set $\{v\in\Sigma^{l}|U(v)\not\subset V\}$ .

Then $\bigcup_{v\in K}U(v)=U-V$. The number of aU the elements of $K$ is $n^{l}(1-b)$ .
Thus, the following equations hold:$X-V=X \cap(\bigcup_{v\in K}U(v))=\bigcup_{v\in K}X\cap U(v)=\bigcup_{v\in K}v\cdot(X/v)$.

By Lemma 4.12, $\mu(X/v)=m$ , hence by Proposition 4.8,$\mu(X-V)=\sum_{v\in K}n^{-l}\mu(X/v)=(1-b)\cdot m$.

Therefore,$\mu(X\cup V)=\mu(V)+\mu(X-V)=b+m(1-b)=m+b(1-m)>m+\epsilon$ .

On the other hand,$X \subset\bigcup_{:\in I}U(w:)$

and$V \subset\bigcup_{:\in I}U(w:)$

Thus$X \cup V\subset\bigcup_{:\in I}U(w:)$.

.

Therefore$\mu(X\cup V)\leq\mu(\bigcup_{:\in I}U(w_{i}))<m+\epsilon$.

Those make contradiction.

1

Lemma 4.14 The measure of a sparse set is 0.
Proof. Let $X\subset U$ be sparse. Put $\mathrm{Y}\in S(X)$ as $\mu(\mathrm{Y})=\max\{\mu(Z)|Z\in \mathrm{S}(\mathrm{X})$ .
Such exists because $S(X)$ is finite. Put
as
and
.
Then
. Hence$w\in\Sigma^{*}$$\mathrm{Y}$$\mathrm{Y}/w=\emptyset$$l=\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(w)$$\mathrm{Y}=\cup\{\mathrm{Y}/v|v\in\Sigma^{*},\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(v)=l\}\Sigma$$\mu(\mathrm{Y})=\mu(\mathrm{Y}/w)+\mu(\mathrm{Y}/v)\leq\sum_{1\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\mathrm{v})=l,v\neq w\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(\mathrm{v})=l,v\neq w}\mu(\mathrm{Y})$$=(1-2^{-l})\mu(\mathrm{Y})$.

, which impUes
because $\mathrm{Y}/v\in S(X)$ . Thus,
We havebecause of $X\in S(X)$ , therefore $\mu(X)=0$ .
$\mu(\mathrm{Y})\leq(1-2^{-l})\mu(\mathrm{Y})$$\mu(X)\leq\mu(\mathrm{Y})$$\mu(\mathrm{Y})=0$

.
1

122
Lemma 4.15 The measure of.a finite\rightarrow state set is mtiond.
Proof. By the detachment lemma 3.13,$\mathrm{Y}_{\dot{1}}$$X=Z \cup\bigcup_{:\in I}W.\cdot\cdot$

where

$Z$

is sparse, theindexed set I is finite, eachis aregular language, eachis regular, and all thesummands of the union operator are disjoint to each other.
By Proposition 4.8, we have
, hence $\mu(X)=\mu(Z)+$$W_{}$$\mathrm{Y}_{\dot{1}}$$\mu(W_{\dot{1}}\cdot \mathrm{Y}_{})=\mu(W_{\dot{1}} .

$\sum_{:\in:}\mu(W_{}\cdot U)\cdot\mu(\mathrm{Y}_{\dot{1}})$

By Lemma 4.13,.

$\mu(\mathrm{Y})$.

By Proposition 4.14, $\mu(Z)=0$ , therefore,$\sum_{j\in J}\mu(W_{j}\cdot U)$

U)\cdot$$\mu(\mathrm{Y})$$\mu(X)=\sum_{:\in:}\mu(W_{\dot{1}} .

U)\cdot\mu(\mathrm{Y}_{\dot{1}})$.

is 1or 0. Put $J=\{j\in I|\mu(\mathrm{Y}_{\mathrm{j}})=1\}$ , Then, $\mu(X)=$This summation is finite. By Lemma 4.10 and Proposition 2.6, each summandis rational. It implies $\mu(X)$ is finite.
1$\mu(W_{j}\cdot U)$

Theorem 4.16 The measure of an omega regular language is rational.
Proof. By Proposition 2.11 and Lemma 4.15.

I

References[It\^o] Ito, S\^ae\^o.: Rubegu Sekibun Nyumon, Sugaku Sensyo, Syokabo, Tokyo, 1963 (inJapanese).

[Biichi] Biichi, J. Richard.: On aDecision Method in Restricted Second Order Arithmetic, Proc. of the International Congress on Logic, Method and Philosophy of
Science, pp. 1-12, Stanford University Press, Stanford, 1962.
[Staiger83] Staiger, L. (1983), Finite state
27, No. 3, pp. 434-448.

$\omega- \mathrm{R}\mathrm{g}\mathrm{a}\mathrm{e}$. J. Comput. System Sci., Vol.

[Thomas] Thomas, W.: Automata on Infinite Objects, Handbook of Theoretical Cornputer Science, Vol. B, van Leeuwen, J. ed., Elsevier Science B. V., 1990.

[Staiger97] Staiger, L:Omega Languages, Handbook of Formal Languages, Rozenberg,
G. &Salomaa, A. eds., Springer, 1997.
[Lin&Yen] Lin,
-Kai&Yen, Hsu-Chun: An omega utomata approach to the com, Electronic Notes in Theoreticalpression of -level images, Proc. of CATS
Science, Vol. 31, No. 1, Elsevier Science B. V., 2000.
$\mathrm{Y}\underline{\mathrm{i}\mathrm{h}}$$\mathrm{b}\mathrm{i}$$Z\theta\theta\theta$$\mathrm{C}\mathrm{o}\mathrm{m}\dot{\mathrm{p}}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}$Acknowledgement
Iam ffeatffil for Lin Yih-Kai, Yamazaki Hideki, Ito Masami, Ludwig Staiger and
Takahashi H. Masako for discussions and comments