AMBIGUITY IN OMEGA CONTEXT FREE LANGUAGES

Olivier Finkel ∗

Equipe de Logique Mathématique CNRS et Université Paris 7, U.F.R. de Mathématiques 2 Place Jussieu 75251 Paris cedex 05, France.

Abstract

We extend the well known notions of ambiguity and of degrees of ambiguity of finitary context free languages to the case of omega context free languages (ω-CFL) accepted by Büchi or Muller pushdown automata. We show that these notions may be defined independently of the Büchi or Muller acceptance condition which is considered. We investigate first properties of the subclasses of omega context free languages we get in that way, giving many examples and studying topological properties of ω-CFL of a given degree of ambiguity.

Key words: context free; language; ω-language; ambiguity; Borel hierarchy; Wadge hierarchy.

Contents

1 Introduction 2

2 ω-regular and ω-context free languages 4

3 Ambiguity 8

4 Borel and projective hierarchies 19

5 Degrees of ambiguity 21

6 Topological properties 30

6.1 Recall of previous results 30

6.2 Wadge hierarchy 32

∗ Corresponding author Email address: finkel@logique.jussieu.fr (Olivier Finkel).

Preprint submitted to Elsevier Science 6.3 Operation of exponentiation of conciliating sets 34

6.4 Borel hierarchy and non ambiguous ω-CFL 47

6.5 Borel hierarchy and ω-CFL which are inherently ambiguous of degree ≤ ℵ_{0}^{−} 48

7 Concluding remarks and further work 58

References 59

1 Introduction

The notion of ambiguity is well known in the theory of finitary context free languages. A context free grammar G is said to be non ambiguous if every word x generated by G is generated via a unique leftmost derivation. A context free language (CFL) L is said to be non ambiguous if it is the language L = L(G) generated by a non ambiguous context free grammar G; otherwise the CFL L is said to be inherently ambiguous. It was proved by Ginsburg and Ullian that one cannot decide whether an arbitrary CFL is inherently ambiguous [GU66]. Every deterministic CFL is non ambiguous [ABB96] but there exist some non deterministic non ambiguous context free languages [Her97]. Maurer gave a proof of the inherent ambiguity of a simple CFL [Mau69]. Some other examples of CFL are shown to be inherently ambiguous by Flajolet using the theory of analytic functions [Fla85] [Fla86]. The notion of inherent ambiguity has been refined by considering degrees of ambiguity, and this led to CFL which are inherently ambiguous of degree k, for k an integer ≥ 2, or of infinite degree. Examples of CFL which are inherently ambiguous of any degree have been given by Maurer in [Mau68]. Crestin proved that the square of the non ambiguous CFL of palindromes is inherently ambiguous of infinite degree [Cre72]. Further examples of CFL which are inherently ambiguous of infinite degree have been recently given by Naji and Wich [Naj98] [Wic99] [Wic00]. Remark that the notion of ambiguity may be studied in an equivalent way from pushdown automata accepting a given CFL, as stated in [Her97], because one can construct, from a context free grammar G generating L, a pushdown automaton M accepting L, and conversely, in such a way that there is a one to one correspondence between leftmost derivations of a word x by G and accepting runs of M on x.

This paper is a first investigation of the extension of the notion of ambiguity to context free languages of infinite words.

ω-languages accepted by finite automata were first studied by Büchi in the sixties in order to prove the decidability of the monadic second order theory of one successor over the integers [Büc60a]. Since then the so called ω-regular languages have been intensively studied. See [Tho90] and [PP01] for many results and references.

As Pushdown automata are a natural extension of finite automata, Cohen and Gold [CG77] [CG78] and Linna [Lin76] studied the ω-languages accepted by omega pushdown automata, considering various acceptance conditions for omega words. It turned out that the omega languages accepted by omega pushdown automata were also those generated by context free grammars where infinite derivations are considered, also studied by Nivat and Boasson in [Niv77]

[Niv78] [BN80]. These languages were then called the omega context free languages (ω-CFL). Topological properties of these ω-languages have been recently studied in [DFR01] [Fin01a] [Fin01b] [Fin00a] [Dup99] [Fin99], in particular in connection with the Borel hierarchy and the Wadge hierarchy which is a great refinement of the Borel hierarchy. See also Staiger’s paper [Sta97a] for a survey of general theory of ω-languages, including more powerful accepting devices, like Turing machines.

In this paper we extend the notion of ambiguity and of degrees of ambiguity to omega context free languages, considered as ω-languages accepted by Büchi or Muller pushdown automata, and investigate the subclasses of the class CF L_{ω} of omega context free languages we obtain in that way. More precisely:

In section 2 we first review some definitions and results about ω-regular and ω-context free languages.

In section 3, we recall some facts about ambiguity in context free finitary languages and we show that non ambiguous Büchi or Muller pushdown automata define the same class of ω-languages which we call the class of non ambiguous ω-context free languages. We then study first closure properties of the class NA − CF L_{ω} of non ambiguous ω-context free languages, showing it is closed under finite disjoint union and intersection with ω-regular languages. We establish some links between the finitary and the infinitary cases which lead to some first examples of inherently ambiguous ω-CFL.

In section 4 we review some definitions and properties of the Borel and projective hierarchies which will be useful in the sequel.

In section 5 we extend to ω-context free languages the usual notion of degree of ambiguity of a finitary context free language. We show that it may be defined independently of the Büchi or Muller acceptance condition which is considered. Then we study first closure properties of the subclasses of CF L_{ω} we have obtained. We state some correspondences between the finitary and the infinitary cases which provide some first examples of ω-CFL which are inherently ambiguous of every finite degree or even of infinite degree.

In section 6 we study topological properties of ω-CFL in connection with their degrees of ambiguity. Using Duparc’s results on the Wadge hierarchy of Borel sets [Dup01], we prove that, for every integer n ≥ 1, there exist some ω-CFL which are non ambiguous or inherently ambiguous of each finite degree or even of infinite degree and which are Σ_{n}^{0} (respectively Π_{n}^{0})-complete Borel sets.

2 ω-regular and ω-context free languages

We assume the reader to be familiar with the theory of formal languages and of ω-regular languages, see for example [HU69] [Tho90]. We first recall some of the definitions and results concerning ω-regular and ω-context free languages and omega pushdown automata as presented in [Tho90] [CG77] [CG78]. When Σ is a finite alphabet, a finite nonempty string (word) over Σ is any sequence x = x_{1} … x_{k} , where x_{i} ∈ Σ for i = 1, …, k and k is an integer ≥ 1. The length of x is k, denoted by |x|. x^{R} = x_{k} … x_{1} is the mirror image of the word x. If |x| = 0, x is the empty word (containing zero letters) denoted by λ. We write x(i) = x_{i} and x[i] = x(1) … x(i) for i ≤ k and x[0] = λ. Σ^{⋆} is the set of finite words over Σ. The first infinite ordinal is ω. An ω-word over Σ is an ω -sequence a_{1} … a_{n} …, where a_{i} ∈ Σ, ∀i ≥ 1. When σ is an ω-word over Σ, we write σ = σ(1)σ(2) … σ(n) … and σ[n] = σ(1)σ(2) … σ(n) the finite word of length n, prefix of σ. The set of ω-words over the alphabet Σ is denoted by Σ^{ω}. An ω-language over an alphabet Σ is a subset of Σ^{ω}.

The usual concatenation product of two finite words u and v is denoted u.v (and sometimes just uv). This product is extended to the product of a finite word u and an ω-word v: the infinite word u.v is then the ω-word such that: (u.v)(k) = u(k) if k ≤ |u| , and (u.v)(k) = v(k − |u|) if k > |u|.

For V ⊆ Σ^{⋆}, V^{ω} = {σ = u_{1} … u_{n} … ∈ Σ^{ω} | u_{i} ∈ V, ∀i ≥ 1} is the ω-power of V. For V ⊆ Σ^{⋆}, the complement of V (in Σ^{⋆}) is Σ^{⋆} − V denoted V^{−}. For a subset A ⊆ Σ^{ω}, the complement of A is Σ^{ω} − A denoted A^{−}.

The prefix relation is denoted ⊑: the finite word u is a prefix of the finite word v (denoted u ⊑ v) if and only if there exists a (finite) word w such that v = u.w. This definition is extended to finite words which are prefixes of ω-words: the finite word u is a prefix of the ω-word v (denoted u ⊑ v) iff there exists an ω-word w such that v = u.w.

For u ∈ Σ^{⋆} or u ∈ Σ^{ω}, the set of (finite) left factors (or prefixes) of u is

LF (u) = {v ∈ Σ^{⋆} | v ⊑ u}

This definition is extended to a finitary language L ⊆ Σ^{⋆} or to an ωlanguage L ⊆ Σ^{ω}:

LF (L) = ⋃_{u∈L} LF (u) = {v ∈ Σ^{⋆} | ∃u ∈ L such that v ⊑ u}

We can now define finite state machines and Büchi and Muller automata:

Definition 2.1 : A finite state machine (FSM) is a quadruple M = (K, Σ, δ, q_{0}), where K is a finite set of states, Σ is a finite input alphabet, q_{0} ∈ K is the initial state and δ is a mapping from K × Σ into 2^{K}. A FSM is called deterministic (DFSM) iff : δ : K × Σ → K. A Büchi automaton (BA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a finite state machine and F ⊆ K is the set of final states. A Muller automaton (MA) is a 5-tuple M = (K, Σ, δ, q_{0}, F) where M′ = (K, Σ, δ, q_{0}) is a FSM and F ⊆ 2^{K} is the collection of designated state sets. A Büchi or Muller automaton is said deterministic if the associated FSM is deterministic. Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. A sequence of states r = q_{1}q_{2} … q_{n} … is called an (infinite) run of M = (K, Σ, δ, q_{0}) on σ, starting in state p, iff: 1) q_{1} = p and 2) for each i ≥ 1, q_{i+1} ∈ δ(q_{i}, a_{i}). In case a run r of M on σ starts in state q_{0}, we call it simply ”a run of M on σ ” . For every (infinite) run r = q_{1}q_{2} … q_{n} … of M, In(r) is the set of states in K entered by M infinitely many times during run r: In(r) = {q ∈ K | {i ≥ 1/q_{i} = q} is infinite }. For M = (K, Σ, δ, q_{0}, F) a BA, the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} | there exists a run r of M on σ such that In(r) ∩ F ≠ ∅}. For M = (K, Σ, δ, q_{0}, F) a MA, the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} | there exists a run r of M on σ such that In(r) ∈ F }.

The classical result of Mc Naughton [MaN66] established that the expressive power of deterministic MA (DMA) is equal to the expressive power of non deterministic MA (NDMA) which is also equal to the expressive power of non deterministic BA (NDBA). There is also a characterization of the languages accepted by MA by means of the ”ω-Kleene closure”:

Definition 2.2 For any family L of finitary languages the ω-Kleene closure of L, is :

ω − KC(L) = {∪_{i=1}^{n}U_{i}.V_{i}^{ω} | U_{i}, V_{i} ∈ L, ∀i ∈ [1, n]}

Theorem 2.3 For any ω-language L, the following conditions are equivalent:

(1) L belongs to ω−KC(REG) , where REG is the class of (finitary) regular languages.

(2) There exists a DMA that accepts L.

(3) There exists a MA that accepts L.

(4) There exists a BA that accepts L.

An ω-language L satisfying one of the conditions of the above Theorem is called an ω-regular language. The class of ω-regular languages will be denoted by REG_{ω}.

We now define the pushdown machines and the classes of ω-context free languages.

Definition 2.4 A pushdown machine (PDM) is a 6-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}), where K is a finite set of states, Σ is a finite input alphabet, Γ is a finite pushdown alphabet, q_{0} ∈ K is the initial state, Z_{0} ∈ Γ is the start symbol, and δ is a mapping from K × (Σ ∪ {λ}) × Γ to finite subsets of K × Γ^{⋆} . If γ ∈ Γ^{+} describes the pushdown store content, the leftmost symbol will be assumed to be on ” top” of the store. A configuration of a PDM is a pair (q, γ) where q ∈ K and γ ∈ Γ^{⋆}. For a ∈ Σ ∪ {λ}, γ, β ∈ Γ^{⋆} and Z ∈ Γ, if (p, β) is in δ(q, a, Z), then we write a : (q, Zγ) ↦_{M} (p, βγ). ↦_{M}^{⋆} is the transitive and reflexive closure of ↦_{M}. (The subscript M will be omitted whenever the meaning remains clear). Let σ = a_{1}a_{2} … a_{n} be a finite word over Σ. A finite sequence of configurations r = (q_{i}, γ_{i})_{1≤i≤p} is called a run of M on σ, starting in configuration (p, γ), iff:

(1) (q_{1}, γ_{1}) = (p, γ)

(2) for each i, 1 ≤ i ≤ (p − 1), there exists b_{i} ∈ Σ ∪ {λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}) such that a_{1}a_{2} … a_{n} = b_{1}b_{2} … b_{p−1}

Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. An infinite sequence of configurations r = (q_{i}, γ_{i})_{i≥1} is called a run of M on σ, starting in configuration (p, γ), iff:

(1) (q_{1}, γ_{1}) = (p, γ)

(2) for each i ≥ 1, there exists b_{i} ∈ Σ ∪ {λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}) such that either a_{1}a_{2} … a_{n} … = b_{1}b_{2} … b_{n} … or b_{1}b_{2} … b_{n} … is a finite prefix of a_{1}a_{2} … a_{n} …

The run r is said to be complete when a_{1}a_{2} … a_{n} … = b_{1}b_{2} … b_{n} …

As for FSM, for every such run, In(r) is the set of all states entered infinitely often during run r. A complete run r of M on σ, starting in configuration (q_{0}, Z_{0}), will be simply called ” a run of M on σ ”.

Recall first the notion of PDA:

Definition 2.5 A pushdown automaton (PDA) is a 7-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ K is the set of final states. The (finitary) language accepted by M is L(M) = {σ ∈ Σ^{⋆} | there exists a run r = (q_{i}, γ_{i})_{1≤i≤p} of M on σ such that q_{p} ∈ F }.

Definition 2.6 A finitary language is context free iff it is accepted by a PDA (by final states). The class of context free languages will be denoted CF L.

Remark 2.7 Other accepting conditions by PDA have been shown to be equivalent to the acceptation condition by final states. Let us cite, [ABB96]:

(a) Acceptation by empty storage.

(b) Acceptation by final states and empty storage.

(c) Acceptation by topmost stack letter.

(d) Acceptation by final states and topmost stack letter.

Return now to the acceptation of infinite words by pushdown automata:

Definition 2.8 A Büchi pushdown automaton (BPDA) is a 7-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ K is the set of final states. The ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} | there exists a complete run r of M on σ such that In(r) ∩ F ≠ ∅}.

Definition 2.9 A Muller pushdown automaton (MPDA) is a 7-tuple M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ 2^{K} is the collection of designated state sets. The ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} | there exists a complete run r of M on σ such that In(r) ∈ F }.

Remark 2.10 We consider here two acceptance conditions for ω-words, the Büchi and the Muller acceptance conditions, respectively denoted 2-acceptance and 3-acceptance in [Lan69] and in [CG78] and (inf, ⊓) and (inf, =) in [Sta97a].

Cohen and Gold, and independently Linna, established a characterization Theorem for ω-CFL:

Theorem 2.11 Let CF L be the class of context free (finitary) languages. Then for any ω-language L the following three conditions are equivalent:

(1) L ∈ ω − KC(CF L).

(2) There exists a BP DA that accepts L.

(3) There exists a MP DA that accepts L.

In [CG77] are also studied the ω-languages generated by ω-context free grammars and it is shown that each of the conditions 1), 2), and 3) of the above Theorem is also equivalent to: 4) L is generated by a context free grammar G by leftmost derivations. These grammars are also studied in [Niv77] [Niv78]. So we set the following definition:

Definition 2.12 An ω-language is an ω-context free language (ω-CFL) iff it satisfies one of the conditions of the above Theorem.

Unlike the case of finite automata, deterministic MP DA do not define the same class of ω-languages as non deterministic MP DA. Let us now define deterministic pushdown machines.

Definition 2.13 A P DM M = (K, Σ, Γ, δ, q_{0}, Z_{0}) is said to be deterministic (DP DM) iff for each q ∈ K, Z ∈ Γ, and a ∈ Σ:

(1) δ(q, a, Z) contains at most one element,

(2) δ(q, λ, Z) contains at most one element, and

(3) if δ(q, λ, Z) is non empty, then δ(q, a, Z) is empty for all a ∈ Σ.

It turned out that the class of ω-languages accepted by deterministic BP DA is strictly included into the class of ω-languages accepted by deterministic MP DA. Let us denote DCF L_{ω} this latest class, the class of omega deterministic context free languages (ω-DCFL), and DCF L the class of deterministic context free (finitary) languages. Then recall the following:

Proposition 2.14 (1) DCF L_{ω} is closed under complementation, but not

under union, neither under intersection.

(2) DCF L_{ω} ⊊ ω − KC(DCF L) ⊊ CF L_{ω} (these inclusions are strict).

Remark 2.15 If M is a deterministic pushdown machine, then for every σ ∈ Σ^{ω}, there exists at most one run r of M on σ determined by the starting configuration.

3 Ambiguity

Remark 3.1 From now on we shall have to count the number of accepting runs of a PDA (respectively, of a BPDA, a MPDA) M on a finite word σ = a_{1}a_{2} … a_{n} (respectively, on a infinite word σ = a_{1}a_{2} … a_{n} …) over Σ.

It is then natural to distinguish two computations of M on σ for which M enters in the same sequence (respectively, infinite sequence) of configurations but for which λ-transitions of M do not occur at the same steps of the runs.

So we shall slightly modify the definition 2.4 of a run of a PDM M as follows.

A run of M on σ, starting in configuration (p, γ) will be a finite sequence r = (q_{i}, γ_{i}, ε_{i})_{1≤i≤p} where (q_{i}, γ_{i})_{1≤i≤p} is a finite sequence of configurations of M and for all i, 1 ≤ i ≤ p, ε_{i} ∈ {0, 1} and:

(1) (q_{1}, γ_{1}) = (p, γ)

(2) for each i, 1 ≤ i ≤ (p − 1), there exists b_{i} ∈ Σ ∪ {λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}), and [ε_{i} = 0 iff b_{i} = λ] and such that a_{1}a_{2} … a_{n} = b_{1}b_{2} … b_{p−1}.

(3) ε_{p} = 0

Let σ = a_{1}a_{2} … a_{n} … be an ω-word over Σ. A run of M on σ, starting in configuration (p, γ) will be an infinite sequence r = (q_{i}, γ_{i}, ε_{i})_{i≥1} where (q_{i}, γ_{i})_{i≥1} is an infinite sequence of configurations of M and, for all i ≥ 1, ε_{i} ∈ {0, 1} and:

(1) (q_{1}, γ_{1}) = (p, γ)

(2) for each i ≥ 1, there exists b_{i} ∈ Σ ∪ {λ} satisfying b_{i} : (q_{i}, γ_{i}) ↦_{M} (q_{i+1}, γ_{i+1}) and ε_{i} = 0 iff b_{i} = λ and such that either a_{1}a_{2} … a_{n} … = b_{1}b_{2} … b_{n} … or b_{1}b_{2} … b_{n} … is a finite prefix of a_{1}a_{2} … a_{n} …

In(r) is still the set of all states entered infinitely often during run r. A complete run is defined as above. A complete run r of M on σ, starting in configuration (q_{0}, Z_{0}), will be simply called ” a run of M on σ ”.

We are going now to recall some known facts about ambiguity.

The notion of ambiguity was first defined for context free grammars generating finite words. A context free grammar G is said to be non ambiguous iff for every word x in the language L(G) generated by G, there exists a unique leftmost derivation of x in G, [GU66].

One may also consider pushdown automata as accepting devices by final states. But for every context free grammar G one can construct a PDA M such that L(M) = L(G) and vice versa, [ABB96]. Since for every word x ∈ L(M) = L(G) there is a one to one correspondence between leftmost derivations of x in G and accepting runs of M on x, the notion of ambiguity defined from PDA in the following way is equivalent to the preceding one. Then from now on we shall refer to pushdown automata as accepting devices and forget the generation by grammars.

Definition 3.2 Let M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) be a pushdown automaton where F ⊆ K is the set of final states. The PDA M is said to be non ambiguous iff for every word σ in L(M) there exists a unique accepting run of M on σ.

Definition 3.3 A context free (finitary) language L is said to be non ambiguous iff it is accepted by a non ambiguous P DA. In the other case L is said to be inherently ambiguous. In that case each P DA which accepts L is ambiguous. The class of non ambiguous context free languages is denoted NA−CF L. The class of inherently ambiguous context free languages is denoted A − CF L.

Remark 3.4 One can easily construct from a PDA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) accepting by final states an equivalent pushdown automaton accepting by final states and topmost stack letters, i.e. M′ = (K′, Σ, Γ′, δ′, q′_{0}, Z′_{0}, (F′, Z′)) where (K′, Σ, Γ′, δ′, q′_{0}, Z′_{0}) is a PDM and F′ ⊆ K is the set of final states and Z′ ⊆ Γ′. A word x ∈ Σ^{⋆} is accepted by M′ iff there exists a run r = (q_{i}, γ_{i}, ε_{i})_{1≤i≤p} of M′ on x such that q_{p} ∈ F′ and γ_{p} = z.γ for z ∈ Z′ and γ ∈ Γ^{⋆}. And conversely, from a PDA M′ accepting by final states and topmost stack letters, one can easily construct an equivalent pushdown automaton accepting (only) by final states. Since there is a one to one correspondence between accepting runs of M on x and accepting runs of M′ on x, the definition of non ambiguous CFL via pushdown automata accepting by final states and topmost stack letters leads to the same classes NA − CF L and A − CF L.

We now define the notion of non ambiguous BP DA or MP DA:

Definition 3.5 Let M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) be a Büchi pushdown automaton where F ⊆ K is the set of final states. The BPDA M is said to be non ambiguous iff for every word σ in L(M) there exists a unique accepting run of M on σ, i.e. a unique complete run r of M on σ such that In(r) ∩ F ≠ ∅.

Definition 3.6 Let M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) be a Muller pushdown automaton where F ⊆ 2^{K} is the collection of designated state sets. The MPDA M is said to be non ambiguous iff for every word σ in L(M) there exists a unique accepting run of M on σ, i.e. a unique complete run r of M on σ such that In(r) ∈ F.

We shall prove that the class of non ambiguous BP DA and the class of non ambiguous MP DA define the same ω-languages:

Theorem 3.7 Let L be an omega context free language. Then L is accepted by a non ambiguous BP DA if and only if it is accepted by a non ambiguous MP DA.

Proof. Let M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) be a Büchi pushdown automaton (BPDA) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ K is the set of final states. Then the ω-language accepted by M is L(M) = {σ ∈ Σ^{ω} / there exists a complete run r of M on σ such that In(r) ∩ F ≠ ∅}. This ω-language is also accepted by the Muller pushdown automaton M_{1} = (K, Σ, Γ, δ, q_{0}, Z_{0}, F_{1}) where F_{1} ⊆ 2^{K} is the set of subsets of K which contain at least one state in F:

F_{1} = {P ⊆ K | P ∩ F ≠ ∅}

Then the machines M and M_{1} differ only by their accepting conditions and it is easy to see that they accept the same language: L(M) = L(M_{1}). Moreover, for each word σ ∈ Σ^{ω}, there is a one to one correspondence between accepting runs of M on σ and accepting runs of M_{1} on σ. Thus if M is non ambiguous the MP DA M_{1} is also non ambiguous.

Conversely assume that M_{2} = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) is a Muller pushdown automaton where F = {F_{1}, …, F_{n}} is the collection of designated state sets. The ω-language accepted by M_{2} is L(M_{2}) = {σ ∈ Σ^{ω} / there exists a complete run r of M_{2} on σ such that In(r) ∈ F }. We shall construct a Büchi pushdown automaton which accepts the same language and remain unambiguous if M_{2} is unambiguous.

Describe first informally the behaviour of the new BP DA M_{3} we are going to construct.

The BP DA M_{3} begins to work like M_{2} but at some appropriate instant, the machine M_{3} will guess that it is for the last time in a state which is not in F_{i}, for 1 ≤ i ≤ n. Then the run will be accepting iff M_{3} enters infinitely often in each state of F_{i}.

More formally we define

M_{3} = (K′, Σ, Γ, δ′, q′_{0}, Z_{0}, F′)

where

K′ = K ∪ {q′_{0}} ∪ ⋃_{i=1}^{n}{i} × F_{i} × (2^{F_{i}} − {∅})

F′ = {(i, q, F_{i}) | q ∈ F_{i} and 1 ≤ i ≤ n}

and the transition relation is defined by the following transition rules:

(a) (q_{0}, Z_{0}) ∈ δ′(q′_{0}, λ, Z_{0}).

(b) ((i, q_{0}, {q_{0}}), Z_{0}) ∈ δ′(q′_{0}, λ, Z_{0}) iff q_{0} ∈ F_{i}, for 1 ≤ i ≤ n.

And for a ∈ Σ ∪ {λ}, γ ∈ Γ^{⋆}, Z ∈ Γ and (p, γ) ∈ δ(q, a, Z):

(c) If q ∉ F_{i} and p ∈ F_{i} then (p, γ) ∈ δ′(q, a, Z) and ((i, p, {p}), γ) ∈ δ′(q, a, Z).

(d) If P = F_{i} and p ∈ F_{i}, then ((i, p, {p}), γ) ∈ δ′((i, q, P), a, Z).

(e) If P ≠ F_{i} and p ∈ F_{i}, ((i, p, P ∪ {p}), γ) ∈ δ′((i, q, P), a, Z).

The equality L(M_{2}) = L(M_{3}) holds by construction. Moreover, for each word σ ∈ Σ^{ω}, there is a one to one correspondence between accepting runs of M_{2} on σ and accepting runs of M_{3} on σ. Thus if M_{2} is non ambiguous the BP DA M_{3} is also non ambiguous. □

Then one can set the following:

Definition 3.8 An omega context free language L is said to be non ambiguous iff it is accepted by a non ambiguous MP DA (or equivalently by a non ambiguous BP DA). In the other case L is said to be inherently ambiguous. In that case each MP DA or BP DA which accepts L is ambiguous. The class of non ambiguous omega context free languages is denoted NA−CF L_{ω}. The class of inherently ambiguous omega context free languages is denoted A − CF L_{ω}.

Remark 3.9 The above construction is similar to Arnold’s construction of a non ambiguous BA accepting the same ω-regular language as a given deterministic MA (which is non ambiguous). Each ω-regular language is accepted by a deterministic MA thus each ω-regular language is accepted by a non ambiguous BA, [Arn83b]. But in the case of pushdown automata, there exist some omega context free languages which are not accepted by any deterministic pushdown automaton and even by any non ambiguous MPDA. But starting with a non ambiguous MPDA M_{2} one can construct a non ambiguous BPDA M_{3} which accepts the same language. We shall see later that the same construction is also useful in the study of degrees of ambiguity for ω-CFL.

Example 3.10 Every ω-CFL which is accepted by a deterministic MPDA is of course a non ambiguous ω-CFL. For example each ω-regular language is a non ambiguous ω-CFL, as well as the following ω-language over the alphabet {a, b, c}:

L = {a^{n}.b^{n} | n ≥ 1}.c.{a, b, c}^{ω}

The class of non ambiguous CFL is closed under intersection with regular languages. This result may be extended to the case of ω-languages:

Theorem 3.11 The class of non ambiguous ω-CFL is closed under intersection with ω-regular languages.

Proof. Let L = L(M) be a non ambiguous ω-CFL accepted by a non ambiguous MPDA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) and L′ = L(M′) be an ω-regular language accepted by a deterministic MA M′ = (K′, Σ, δ′, q′_{0}, F′).

The ω-language L∩L′ is accepted by a MPDA which is the classical product of the two machines M and M′ with appropriate acceptance conditions. More formally let M′′ be the MPDA M′′ = (K′′, Σ, Γ, δ′′, (q_{0}, q′_{0}), Z_{0}, F′′), where

K′′ = K × K′

and the transition relation δ′′ is defined by the following transition rules:

(1) ((q, q′), ν) ∈ δ′′((p, p′), a, γ) iff (q, ν) ∈ δ(p, a, γ) and δ′(p′, a) = q′, for each a ∈ Σ and γ ∈ Γ and ν ∈ Γ^{⋆} and p, q ∈ K and p′, q′ ∈ K′.

(2) ((q, p′), ν) ∈ δ′′((p, p′), λ, γ) iff (q, ν) ∈ δ(p, λ, γ), for each γ ∈ Γ and ν ∈ Γ^{⋆} and p, q ∈ K and p′ ∈ K′.

And the collection of designated state sets F′′ is defined by: a subset S of K′′ is in F′′ if and only if its projection proj_{K}(S) onto K is in F and its projection proj_{K′}(S) onto K′ is in F′.

It is clear that the MPDA accepts L ∩ L′ and that for each ω-word σ ∈ Σ^{ω} accepted by M′′, there exists a unique accepting run of M′′ on σ because M is non ambiguous and M′ is deterministic. □

In the case of context free languages one can derive first properties of non ambiguous (respectively inherently ambiguous) ω-CFL from the finitary case. Let us state firstly the following result.

Proposition 3.12 Let V ⊆ Σ^{⋆} be a finitary context free language over the alphabet Σ and d be a new letter not in Σ, then the following equivalences hold:

(a) V.d^{ω} is in NA − CF L_{ω} iff V is in NA − CF L.

(b) V.d.(Σ ∪ {d})^{ω} is in NA − CF L_{ω} iff V is in NA − CF L.

Proof. (a) Assume first that V is a non ambiguous context free finitary language. Then there exists a non ambiguous P DA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) where M′ = (K, Σ, Γ, δ, q_{0}, Z_{0}) is a PDM and F ⊆ K is the set of final states such that L(M) = V. We shall define a non ambiguous BPDA which accepts the ω-language V.d^{ω}. Let M′′ be the PDM M′ to which we add another state q_{f} and whose transition relation δ′′ is just δ to which we add the following transition rules: For q ∈ F and Z ∈ Γ, (q_{f}, Z) is in δ′′(q, d, Z) and (q_{f}, Z) is in δ′′(q_{f}, d, Z).

Now consider the BPDA N = (K ∪ {q_{f}}, Σ ∪ {d}, Γ, δ′′, q_{0}, Z_{0}, {q_{f}}). The set of final states of N is just {q_{f}}. Then it is easy to see that L(N) = V.d^{ω} and that N is non ambiguous because M was non ambiguous. Thus the ωlanguage V.d^{ω} is a non ambiguous ω-CFL.

Conversely assume that V.d^{ω} is a non ambiguous ω-CFL. By Theorem 2.11 there exist some context free finitary languages U_{i} and V_{i}, for 1 ≤ i ≤ n, such that

V.d^{ω} = ⋃_{1≤i≤n} U_{i}.V_{i}^{ω}

Recall now the way Linna proved that the class of ω-CFL is equal to the omega Kleene closure of the class of context free finitary languages, [Lin76] [Sta97a].

Let L = L(M) be an ω-CFL accepted by a BPDA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F). Define for all pairs (p, z) ∈ K × Γ and all q ∈ K the following context free languages:

V_{(p,z)} = {σ ∈ Σ^{⋆} | there exists a run of M on σ starting in configuration (q_{0}, Z_{0}) and ending in a configuration (p, z.γ) for γ ∈ Γ^{⋆}}

This may be written :

V_{(p,z)} = {σ ∈ Σ^{⋆} | σ : (q_{0}, Z_{0}) ↦_{M}^{⋆} (p, z.γ) for γ ∈ Γ^{⋆}}

Define also

W_{(p,z)}^{q} = {σ ∈ Σ^{+} | there exists a run of M on σ starting in a configuration (p, z) and ending in a configuration (p, zγ) for γ ∈ Γ^{⋆} and such that M enters in state q during the run}

We can now express the ω-language accepted by the BPDA M by means of the languages V_{(p,z)} and W_{(p,z)}^{q} which are finitary context free languages:

L(M) = ⋃_{(p,z)∈K×Γ and q∈F} V_{(p,z)}.(W_{(p,z)}^{q})^{ω}

Return now to the case L(M) = V.d^{ω}, where V.d^{ω} is a non ambiguous ω-CFL and M = (K, Σ∪{d}, Γ, δ, q_{0}, Z_{0}, F) is a non ambiguous BPDA. Another construction of Linna [Lin76] provides a pushdown automaton accepting V from the BPDA M. We recall it now because it will be useful for our proof and in the next section.

Denote

R = {(p, z) | ( ⋃_{q∈F} W_{(p,z)}^{q}) ∩ {d}^{+} ≠ ∅}

Let then M_{1} be the following P DA:

M_{1} = (K ∪ K′ ∪ {q_{f}}, Σ, Γ, δ_{1}, q_{0}, Z_{0}, {q_{f}})

where K′ = {p′ | p ∈ K}, q_{f} is a new state not in K and and the transition relation δ_{1} is defined by:

(1) δ_{1}(p, a, Z) = δ(p, a, Z) for all p ∈ K, a ∈ Σ and Z ∈ Γ,

(2) δ_{1}(p, λ, Z) = δ(p, λ, Z) ∪ {(q′, γ) | (q, γ) ∈ δ(p, d, Z)} if (p, Z) ∉ R,

(3) δ_{1}(p, λ, Z) = δ(p, λ, Z) ∪ {(q_{f}, λ)} if (p, Z) ∈ R,

(4) δ_{1}(p′, λ, Z) = {(q′, γ) | (q, γ) ∈ δ(p, d, Z) ∪ δ(p, λ, Z)} if (p, Z) ∉ R,

(5) δ_{1}(p′, λ, Z) = {(q_{f}, λ)} if (p, Z) ∈ R,

(6) otherwise δ_{1} is undefined.

The PDA M_{1} accepts the context free language V. In fact M_{1} while reading a word u ∈ Σ^{⋆}, begins the reading as the BPDA M. Some λ-transitions are added to simulate the reading by M of letters d in the ω-word u.d^{ω} until the pushdown automaton reaches a configuration (p, zγ), for γ ∈ Γ^{⋆}, such that (p, z) ∈ R, and this ensures that the word u is in V, otherwise the word u is not in V.

We have assumed that V.d^{ω} is non ambiguous and that M is also non ambiguous. From the definition of M_{1} we can see that for u ∈ V there exists a unique accepting run of M on u.d^{ω} and the simulation of an initial segment of this run by M_{1} is also unique. Hence there exists a unique accepting run of M_{1} on u. Then M_{1} is non ambiguous and so is the context free language V.

(b) As in the proof of (a), one can easily construct, from a non ambiguous PDA M accepting a language V ⊆ Σ^{⋆}, a non ambiguous BPDA N accepting the ω-language V.d.(Σ ∪ {d})^{ω}.

Conversely assume that V.d.(Σ ∪ {d})^{ω} is a non ambiguous ω-CFL, where V ⊆ Σ^{⋆}, and d is a new letter not in Σ. Then the class of non ambiguous ω-CFL being closed under intersection with ω-regular languages, the ωlanguage

V.d^{ω} = V.d.(Σ ∪ {d})^{ω} ∩ Σ^{⋆}.d^{ω}

is non ambiguous and the proof of (a) implies that V is in NA − CF L. □

Remark 3.13 In the second part of the above proof of (a), we have constructed a PDA M_{1} accepting V from a BPDA accepting the ω-language V.d^{ω}. And if M is non ambiguous, M_{1} also is non ambiguous. More generally if a word u.d^{ω}, where u ∈ Σ^{⋆}, admits less than k accepting runs of M, where k is an integer ≥ 1, then the word u admits also less than k accepting runs of M_{1}. This will be useful in the next sections for the study of degrees of ambiguity.

Recall now some examples of inherently ambiguous context free languages, (see [Fla85] [Fla86]), which will provide some inherently ambiguous ω-CFL by proposition 3.12.

Theorem 3.14 ([Fla85][Fla86]) For an integer n ≥ 0 let n̄ = a^{n}b be the unary representation of n over the alphabet Σ = {a, b}. Then the following context free languages G_{≠}, G_{<}, G_{>}, G_{=}, H_{≠} are inherently ambiguous, where:

G_{≠} = {n̄_{1}n̄_{2} … n̄_{p} | for some j n_{j} ≠ j}
G_{<} = {n̄_{1}n̄_{2} … n̄_{p} | for some j n_{j} < j}
G_{>} = {n̄_{1}n̄_{2} … n̄_{p} | for some j n_{j} > j}
G_{=} = {n̄_{1}n̄_{2} … n̄_{p} | for some j n_{j} = j}
H_{≠} = {n̄_{1}n̄_{2} … n̄_{p} | for some j n_{j} ≠ p}

(where the variable p runs over all integers ≥ 1 and the n_{j} over integers ≥ 0.)

From the preceding proposition we can infer some other results about ω-CFL:

Proposition 3.15 The class of non ambiguous context free ω-languages is not closed under finite union. But it is closed under disjoint finite union.

Proof. It is well known that the class of non ambiguous context free finitary languages is not closed under finite union. For instance let

V_{1} = {a^{n}b^{m}c^{p} | n, m, p are integers ≥ 1 and n = m}
V_{2} = {a^{n}b^{m}c^{p} | n, m, p are integers ≥ 1 and m = p}

It is easy to show that the languages V_{1} and V_{2} are deterministic context free, i.e. that they are accepted by some deterministic pushdown automata. Hence they are non ambiguous context free languages, [ABB96].

But their union V_{1} ∪ V_{2} is a context free language which is known to be inherently ambiguous, [Mau69].

Then if d is a new letter the ω-languages V_{1}.d^{ω} and V_{2}.d^{ω} are non ambiguous ω-CFL but their union

V_{1}.d^{ω} ∪ V_{2}.d^{ω} = (V_{1} ∪ V_{2}).d^{ω}

is an inherently ambiguous ω-CFL by Proposition 3.12.

In order to prove that the class NA − CF L_{ω} is closed under disjoint union, assume now that L_{1} is accepted by a non ambiguous MPDA M_{1} and L_{2} is accepted by a non ambiguous MPDA M_{2} and that L_{1} and L_{2} are disjoint. It is then easy to show that there exists a non ambiguous MPDA M which accepts the ω-language L_{1} ∪ L_{2}. We explain informally this result.

One can assume that the state sets K_{1} and K_{2} of M_{1} and M_{2} are disjoint, and add a new initial state Q_{0}. Then one add some λ-transitions which are used to choose at the first step of runs of M if the new machine simulates next the MPDA M_{1} or the MPDA M_{2}. Let then σ ∈ L_{1} ∪ L_{2}. One can assume without loss of generality that σ ∈ L_{1} and then σ ∉ L_{2} because L_{1} ∩ L_{2} = ∅. There is a unique accepting run of M_{1} on σ thus there is a unique accepting run r of M on σ: the machine M chooses at the first step of the run r (using a λ-transition) to simulate next the machine M_{1} and after this λ-transition the run r of M is identical with the unique accepting run of M_{1} on σ.

The case of a finite number k of non ambiguous ω-CFL is proved by induction on the integer k. □

Proposition 3.16 It is undecidable to determine whether an arbitrary ω-CFL is non ambiguous (respectively inherently ambiguous).

Proof. It is known that it is undecidable to determine whether an arbitrary CFL is non ambiguous (respectively inherently ambiguous), [GU66]. The proposition 3.16 follows then from this result and from proposition 3.12. □

A natural question now arises: does there exist a characterization Theorem analogous to Theorem 2.11 for non ambiguous ω-CFL? The answer is given by the following:

Theorem 3.17 The class of non ambiguous ω-CFL is strictly included into the omega Kleene closure of the class of non ambiguous context free finitary languages:

NA − CF L_{ω} ⊊ ω − KC(NA − CF L)

Proof. Let L = L(M) be an ω-CFL accepted by a BPDA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F). Assume that L(M) is non ambiguous and that M is a non ambiguous BPDA.

Recall Linna defined in [Lin76] for all pairs (p, z) ∈ K × Γ and all q ∈ K the following context free languages:

V_{(p,z)} = {σ ∈ Σ^{⋆} | there exists a run of M on σ starting in configuration (q_{0}, Z_{0}) and ending in a configuration (p, z.γ) for γ ∈ Γ^{⋆}}

V_{(p,z)} = {σ ∈ Σ^{⋆} | σ : (q_{0}, Z_{0}) ↦_{M}^{⋆} (p, z.γ) for γ ∈ Γ^{⋆}}

And

W_{(p,z)}^{q} = {σ ∈ Σ^{+} | there exists a run of M on σ starting in a configuration (p, z) and ending in a configuration (p, zγ) for γ ∈ Γ^{⋆} and such that M enters in state q during the run} Then the ω-language accepted by the BPDA M is

L(M) = ⋃_{(p,z)∈K×Γ and q∈F} V_{(p,z)}.(W_{(p,z)}^{q})^{ω}

In fact this union is restricted to the pairs (p, z) such that V_{(p,z)} is non empty and such that there exists a state q ∈ F such that W_{(p,z)}^{q} is non empty.

We are going to show that these context free languages V_{(p,z)} and W_{(p,z)}^{q} are non ambiguous.

Let σ ∈ Σ^{⋆} be a finite word in such a language V_{(p,z)}. Then there exists an infinite word in L(M) which is in the form σ.u^{ω} with u ∈ W_{(p,z)}^{q} and q ∈ F. But there is a unique accepting run of M on σ.u^{ω}, hence there exists a unique run on σ of the pushdown machine associated with M which starts in the initial configuration and ends in a configuration (p, zγ) for γ ∈ Γ^{⋆}. This ensures that the pushdown automaton accepting V_{(p,z)} by final state p and topmost stack letter z is non ambiguous. As remarked above this implies that V_{(p,z)} is also a ccepted by a non ambiguous PDA accepting by final states. Hence the context free language V_{(p,z)} is non ambiguous.

Consider now a language W_{(p,z)}^{q} such that V_{(p,z)} is non empty and q ∈ F. By definition this language is also accepted by a PDA obtained from M with initial configuration (p, z) and which accepts by accepting states and topmost stack letter z. The exact construction is left to the reader.

Let then σ ∈ Σ^{⋆} be a finite word in V_{(p,z)} and u be a finite (nonempty) word in W_{(p,z)}^{q}. The word σ.u^{ω} is in L(M) thus there exists a unique accepting run of M on σ.u^{ω}. As above this implies that the pushdown automaton accepting W_{(p,z)}^{q} has a unique accepting run on u (it suffices to consider an initial segment of the run on the finite word σ.u). Thus this pushdown automaton is non ambiguous. Hence the language W_{(p,z)}^{q} is non ambiguous.

The inclusion

NA − CF L_{ω} ⊆ ω − KC(NA − CF L)

is then proved. The inclusion is strict because the class NA − CF L_{ω} is not closed under finite union but ω − KC(NA − CF L) is. □

One may ask for a similar result about the class of inherently ambiguous omega context free languages. But we shall prove the following

Theorem 3.18 The class of inherently ambiguous ω-CFL is not included into the omega Kleene closure of the class of inherently ambiguous context free finitary languages:

A − CF L_{ω} ⊈ ω − KC(A − CF L)

Proof. Let V ⊆ Σ^{⋆} be an inherently ambiguous context free finitary language and d be a new letter not in Σ. By Proposition 3.12 the ω-language V.d^{ω} is an inherently ambiguous ω-CFL. On the other hand by Theorem 2.11 there exist some context free languages U_{i} and V_{i}, for 1 ≤ i ≤ n, such that

V.d^{ω} = ⋃_{1≤i≤n} U_{i}.V_{i}^{ω}

But then for all i ∈ [1; n], V_{i} ⊆ d^{⋆}. But it is well known that a context free language over an alphabet containing only one letter is a regular language. Thus the languages V_{i} are deterministic context free languages hence they belong to the class of non ambiguous context free finitary languages. □

We are going now to recall some facts about Borel and projective hierarchies which will be useful in the study of degrees of ambiguity for ω-CFL.

4 Borel and projective hierarchies

We assume the reader to be familiar with basic notions of topology which may be found in [Kur66] [LT94] [Sta97a] [PP01].

Topology is an important tool for the study of ω-languages, and leads to characterization of several classes of ω-languages. For a finite alphabet X, we consider X^{ω} as a topological space with the Cantor topology. The open sets of X^{ω} are the sets in the form W.X^{ω}, where W ⊆ X^{⋆}. A set L ⊆ X^{ω} is a closed set iff its complement X^{ω} − L is an open set. The class of open sets of X^{ω} will be denoted by G or by Σ_{1}^{0}. The class of closed sets will be denoted by F or by Π_{1}^{0}. Closed sets are characterized by the following:

Proposition 4.1 A set L ⊆ X^{ω} is a closed subset of X^{ω} iff for every σ ∈ X^{ω},

[∀n ≥ 1, ∃u ∈ X^{ω} such that σ(1) … σ(n).u ∈ L] implies that σ ∈ L.

Every closed set L ⊆ X^{ω} may be obtained as the adherence of a finitary language. We first recall the notion of adherence.

Definition 4.2 Let V ⊆ X^{⋆} be a finitary language over the alphabet X. The adherence of the language V is

Adh(V) = {σ ∈ X^{ω} / LF (σ) ⊆ LF (V)}

We can now state the following result.

Proposition 4.3 (see [Sta97a]) A set L ⊆ X^{ω} is a closed set of X^{ω} iff there exists a finitary language V ⊆ X^{⋆} such that L = Adh(V).

Define now the next classes of the Borel Hierarchy:

Definition 4.4 The classes Σ_{n}^{0} and Π_{n}^{0} of the Borel Hierarchy on the topological space X^{ω} are defined as follows: Σ_{1}^{0} is the class of open sets of X^{ω}. Π_{1}^{0} is the class of closed sets of X^{ω}. Π_{2}^{0} or G_{δ} is the class of countable intersections of open sets of X^{ω}. Σ_{2}^{0} or F_{σ} is the class of countable unions of closed sets of X^{ω}. And for any integer n ≥ 1: Σ_{n+1}^{0} is the class of countable unions of Π_{n}^{0}-subsets of X^{ω}. Π_{n+1}^{0} is the class of countable intersections of Σ_{n}^{0}-subsets of X^{ω}. The Borel Hierarchy is also defined for transfinite levels. The classes Σ_{α}^{0} and Π_{α}^{0}, for a countable ordinal α, are defined in the following way: Σ_{α}^{0} is the class of countable unions of subsets of X^{ω} in ∪_{γ<α}Π_{γ}^{0}. Π_{α}^{0} is the class of countable intersections of subsets of X^{ω} in ∪_{γ<α}Σ_{γ}^{0}.

Recall some basic results about these classes, [Mos80]:

Proposition 4.5

(a) Σ_{α}^{0} ∪ Π_{α}^{0} ⊊ Σ_{α+1}^{0} ∩ Π_{α+1}^{0}, for each countable ordinal α ≥ 1.

(b) ∪_{γ<α}Σ_{γ}^{0} = ∪_{γ<α}Π_{γ}^{0} ⊊ Σ_{α}^{0} ∩ Π_{α}^{0}, for each countable limit ordinal α.

(c) A set W ⊆ X^{ω} is in the class Σ_{α}^{0} iff its complement is in the class Π_{α}^{0}.

(d) Σ_{α}^{0} − Π_{α}^{0} ≠ ∅ and Π_{α}^{0} − Σ_{α}^{0} ≠ ∅ hold for every countable ordinal α ≥ 1.

(e) For every ordinal α ≥ 1, the class Σ_{α}^{0} is closed under countable unions and the class Π_{α}^{0} is closed under countable intersections.

We shall say that a subset of X^{ω} is a Borel set of rank α, for a countable ordinal α, iff it is in Σ_{α}^{0} ∪ Π_{α}^{0} but not in ⋃_{γ<α}(Σ_{γ}^{0} ∪ Π_{γ}^{0}).

There is a nice characterization of Π_{2}^{0}-subsets of X^{ω}. First define the notion of W^{δ}:

Definition 4.6 For W ⊆ X^{⋆}, let W^{δ} = {σ ∈ X^{ω} | ∃^{ω}i such that σ[i] ∈ W }. (σ ∈ W^{δ} iff σ has infinitely many prefixes in W).

Then we can state the following Proposition:

Proposition 4.7 (see [Sta97a]) A subset L of X^{ω} is a Π_{2}^{0}-subset of X^{ω} iff there exists a set W ⊆ X^{⋆} such that L = W^{δ}.

For X a finite set, (and this is also true if X is an infinite alphabet) there are some subsets of X^{ω} which are not Borel sets. Indeed there exists another hierarchy beyond the Borel hierarchy, which is called the projective hierarchy and which is obtained from the Borel hierarchy by successive applications of operations of projection and complementation. More precisely, a subset A of X^{ω} is in the class Σ_{1}^{1} of analytic sets iff there exists another finite set Y and a Borel subset B of (X × Y)^{ω} such that x ∈ A ↔ ∃y ∈ Y^{ω} such that (x, y) ∈ B. We denote (x, y) the infinite word over the alphabet X×Y such that (x, y)(i) = (x(i), y(i)) for each integer i ≥ 0. Now a subset of X^{ω} is in the class Π_{1}^{1} of coanalytic sets iff its complement in X^{ω} is an analytic set. The next classes are defined in the same manner, Σ_{n+1}^{1}-sets of X^{ω} are projections of Π_{n}^{1}-sets and Π_{n+1}^{1}-sets are the complements of Σ_{n+1}^{1}-sets.

Recall also the notion of completeness with regard to reduction by continuous functions. Let α be a countable ordinal. A set F ⊆ X^{ω} is a Σ_{α}^{0} (respectively Π_{α}^{0})-complete set iff for any set E ⊆ Y^{ω} (with Y a finite alphabet): E ∈ Σ_{α}^{0} (respectively E ∈ Π_{α}^{0}) iff there exists a continuous function f : Y^{ω} → X^{ω} such that E = f^{−1}(F). A similar notion exists for the classes of the projective hierarchy: in particular A set F ⊆ X^{ω} is a Σ_{1}^{1} (respectively Π_{1}^{1})-complete set iff for any set E ⊆ Y^{ω} (Y a finite alphabet): E ∈ Σ_{1}^{1} (respectively E ∈ Π_{1}^{1}) iff there exists a continuous function f : Y^{ω} → X^{ω} such that E = f^{−1}(F).

A Σ_{α}^{0} (respectively Π_{α}^{0})-complete set is a Σ_{α}^{0} (respectively Π_{α}^{0})-set which is in some sense a set of the highest topological complexity among the Σ_{α}^{0} (respectively Π_{α}^{0})-sets. Σ_{n}^{0} (respectively Π_{n}^{0})-complete sets, with n an integer ≥ 1, are thoroughly characterized in [Sta86].

Recall that a set F ⊆ X^{ω} is a Σ_{α}^{0} (respectively Π_{α}^{0})-complete set if and only if it is a Σ_{α}^{0} but not Π_{α}^{0} set (respectively Π_{α}^{0} but not Σ_{α}^{0} set). This follows from Wadge’s study of the now called Wadge hierarchy of Borel sets, see section 6 below and [Wad84] [Dup01].

5 Degrees of ambiguity

The notion of inherently ambiguous CFL has been refined by considering the degrees of ambiguity which we now recall. We use partially the notations of the recent paper of Herzog [Her97], but call ℵ_{0} the cardinal of the countable set of natural numbers, considered also as the supremum of the set of finite cardinals.

Definition 5.1 Let M be a PDA accepting finite words over the alphabet Σ. For x ∈ Σ^{⋆} let α_{M}(x) be the number of accepting runs of M on x, and

(a) If sup{α_{M}(x) | x ∈ Σ^{⋆}} ∈ ℕ, then

α_{M} = sup{α_{M}(x) | x ∈ Σ^{⋆}}

(b) If {α_{M}(x) | x ∈ Σ^{⋆}} is unbounded in ℕ,

then

α_{M} = ℵ_{0}^{−}

We assume now that the set ℕ ∪ {ℵ_{0}^{−}} is linearly ordered by the relation < and that for each integer k ∈ ℕ,

k < k + 1 < ℵ_{0}^{−}

Then we can set the following definition.

Definition 5.2 Let k ∈ ℕ ∪ {ℵ_{0}^{−}}. Let

P DA(α ≤ k) = {M | M is a P DA with α_{M} ≤ k}
P DA(α < k) = {M | M is a P DA with α_{M} < k}
CF L(α ≤ k) = {L(M) | M is a P DA with α_{M} ≤ k}
CF L(α < k) = {L(M) | M is a P DA with α_{M} < k}

A context free language L is said to be inherently ambiguous of degree k, for k an integer ≥ 2 if

L ∈ A(k) − CF L = CF L(α ≤ k) − CF L(α < k)

A context free language L is usually said to be inherently ambiguous of infinite degree if

L ∈ A(ℵ_{0}^{−}) − CF L = CF L(α ≤ ℵ_{0}^{−}) − CF L(α < ℵ_{0}^{−})

In that case we shall say also that L is of degree of ambiguity ℵ_{0}^{−}, (and not just ℵ_{0}), for a reason which will be explained later.

Remark 5.3 For a PDA M accepting finite words over the alphabet Σ, α_{M} is equal to zero if and only if L(M) is the empty set because in that case α_{M}(x) = 0 for all x ∈ Σ^{⋆}. In the other cases α_{M} may be a finite integer ≥ 1 or ℵ_{0}^{−}.

Remark 5.4 The classes CF L(α ≤ k) and CF L(α < k) are defined here by means of PDA accepting by final states. If we consider PDA accepting by final states and topmost stack letters, one can see that the classes CF L(α ≤ k) and CF L(α < k) remain unchanged, using the fact cited in Remark 3.4.

Remark 5.5 For k = ℵ_{0}^{−} the class CF L(α ≤ ℵ_{0}^{−}) is the whole class CF L. For k = 1, the class CF L(α ≤ 1) is the class of non ambiguous context free languages.

The inclusions

CF L(α ≤ k) ⊊ CF L(α ≤ k + 1)

are strict for every integer k ≥ 0. And so is the inclusion

CF L(α < ℵ_{0}^{−}) ⊊ CF L(α ≤ ℵ_{0}^{−})

This may be shown using the following examples due to Maurer [Mau68] and also cited in [Her97].

Example 5.6 Let k be an integer ≥ 2 and let Σ_{k} = {a_{1}, a_{2}, … a_{2k}} be an alphabet having 2k letters and let

A_{k} = ⋃_{i=1}^{k}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}} … a_{2k−1}^{n_{k}}a_{2k}^{n_{k}} | n_{1}, n_{2}, …, n_{k} ≥ 1}

Above n_{1}, n_{2}, … n_{k} are integers ≥ 1 and in a word

a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}} … a_{2k−1}^{n_{k}}a_{2k}^{n_{k}}

for each j, 1 ≤ j < i, letters a_{2j} and a_{2j+1} appear in the segment a_{2j}^{n_{j+1}}.a_{2j+1}^{n_{j+1}}, for each j, i ≤ j < k, letters a_{2j+1} and a_{2j+2} appear in the segment a_{2j+1}^{n_{j+1}}.a_{2j+2}^{n_{j+1}}.

Let also

A_{∞} = A_{2}^{⋆}

Then A_{k} is inherently ambiguous of degree k over the alphabet Σ_{k} and A_{∞} is inherently ambiguous of infinite degree over the alphabet Σ_{2}.

We want now to extend these notions in the context of ω-CFL. We shall consider first BPDA and MPDA. We denote 2^{ℵ_{0}} the cardinal of the continuum which is also the cardinal of the set Σ^{ω} of ω-words over the finite alphabet Σ (having at least two letters).

Lemma 5.7 Let M be a BPDA or MPDA accepting infinite words over the alphabet Σ. For x ∈ Σ^{ω} let α_{M}(x) be the cardinal of the set of accepting runs of M on x. Then

α_{M}(x) ∈ ℕ ∪ {ℵ_{0}, 2^{ℵ_{0}}}

Proof. As indicated in the proof of Theorem 3.7 one can construct, from a MPDA M′, another BPDA M such that L(M) = L(M′) and for every word σ in L(M) = L(M′) there is a one to one correspondence between accepting runs of M on σ and accepting runs of M′ on σ. Hence one can prove the lemma for BPDA first.

Let then M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) be a BPDA, and σ ∈ Σ^{ω}. We shall show that the set of (codes of) accepting runs of M on σ is an analytic set.

To an infinite sequence r = (q_{i}, γ_{i}, ε_{i})_{i≥1}, (where (q_{i}, γ_{i})_{i≥1} is an infinite sequence of configurations and, for each i ≥ 1, ε_{i} ∈ {0, 1}) we associate first an ω-word r̄ over the alphabet Γ ∪ K ∪ {0, 1} defined by

r̄ = q_{1}.γ_{1}.ε_{1}.q_{2}.γ_{2}.ε_{2} … q_{i}.γ_{i}.ε_{i} …

Then to an infinite word σ ∈ Σ^{ω} and an infinite sequence r = (q_{i}, γ_{i}, ε_{i})_{i≥1}, we associate an infinite word (σ × r̄) over the alphabet X = Σ × (Γ ∪ K ∪ {0, 1}) defined by

(σ × r̄)(j) = (σ(j), r̄(j))

for each integer j ≥ 1.

Explain now informally that one can construct a Turing machine T accepting infinite words over the alphabet X = Σ × (Γ ∪ K ∪ {0, 1}) with a Büchi condition and such that an ω-word x ∈ X^{ω} is accepted by T if and only if it is in the form (σ × r̄) where σ ∈ Σ^{ω} and r is an accepting run of M on σ.

But it is well known that the ω-language L(T) accepted by a Turing machine T is an analytic set (see for example [Sta97a]).

Let σ ∈ Σ^{ω} and L(T)|σ be the section of L(T) at point σ defined by: an ω-word x ∈ X^{ω} is in L(T)|σ iff for all i ≥ 1, x(i) = (σ(i), a(i)) for some a(i) ∈ (Γ ∪ K ∪ {0, 1}).

Thus for a fixed ω-word σ ∈ Σ^{ω} the set L(T)|σ is also an analytic set because it is the intersection of the analytic set L(T) with the closed set X^{ω}|σ.

But by Suslin’s Theorem [Mos80], an analytic subset of X^{ω} is either countable or has the continuum power, even if the continuum hypothesis fails (the continuum hypothesis says that every subset of X^{ω} is either countable or has the continuum power, but this has been shown undecidable in the classical axiomatic system ZF of set theory [Sch67]). Then we can infer that the set L(T)|σ and hence the set of accepting runs of M on σ is either countable (and in that case its cardinal is either an integer or ℵ_{0}) or has the continuum power (and in that case its cardinal is 2^{ℵ_{0}}). □

Remark 5.8 Let M be a BPDA or MPDA such that L(M) ⊆ Σ^{ω}. The preceding lemma implies that

sup{α_{M}(x) | x ∈ Σ^{ω}} ∈ ℕ ∪ {ℵ_{0}, 2^{ℵ_{0}}}

In the case sup{α_{M}(x) | x ∈ Σ^{ω}} = ℵ_{0}, two cases may happen:

(a) There exists (at least) one word x ∈ Σ^{ω} such that α_{M}(x) = ℵ_{0}.

(b) There does not exist any word x ∈ Σ^{ω} such that α_{M}(x) = ℵ_{0}.

In order to distinguish these two cases, we shall set the following definition.

Definition 5.9 Let M be a BPDA or MPDA accepting infinite words over the alphabet Σ. Then

(a) If sup{α_{M}(x) | x ∈ Σ^{ω}} ∈ ℕ ∪ {2^{ℵ_{0}}}, then

α_{M} = sup{α_{M}(x) | x ∈ Σ^{ω}}

(b) If sup{α_{M}(x) | x ∈ Σ^{ω}} = ℵ_{0} and there does not exist any word x ∈ Σ^{ω} such that α_{M}(x) = ℵ_{0}, then

α_{M} = ℵ_{0}^{−}

(c) If sup{α_{M}(x) | x ∈ Σ^{ω}} = ℵ_{0} and there exists (at least) one word x ∈ Σ^{ω} such that α_{M}(x) = ℵ_{0}, then

α_{M} = ℵ_{0}

We assume now that the set ℕ∪{ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}} is linearly ordered by the relation < and that for each integer k ∈ ℕ,

k < k + 1 < ℵ_{0}^{−} < ℵ_{0} < 2^{ℵ_{0}}

We can now define a hierarchy of BPDA and MPDA:

Definition 5.10 Let k ∈ ℕ ∪ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}} and

BP DA(α ≤ k) = {M | M is a BP DA with α_{M} ≤ k}
MP DA(α ≤ k) = {M | M is a MP DA with α_{M} ≤ k}
BP DA(α < k) = {M | M is a BP DA with α_{M} < k}
MP DA(α < k) = {M | M is a MP DA with α_{M} < k}

As in the finitary case, the class BP DA(α ≤ 1) (respectively MP DA(α ≤ 1)) is the class of non ambiguous BPDA (respectively MPDA). We have seen in Theorem 3.7 that Büchi or Muller acceptance conditions lead to the same class of non ambiguous omega context free languages. This result may be extended to the other classes defined above:

Theorem 5.11 For all k ∈ ℕ ∪ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}},

{L(M) | M ∈ BP DA(α ≤ k)} = {L(M) | M ∈ MP DA(α ≤ k)}
{L(M) | M ∈ BP DA(α < k)} = {L(M) | M ∈ MP DA(α < k)}

Proof. Return to the proof of Theorem 3.7. We have shown that one can construct, from a BPDA M accepting the ω-language L(M) ⊆ Σ^{ω}, a MPDA M_{1} such that L(M) = L(M_{1}), and vice-versa. Moreover, for every ω-word σ ∈ Σ^{ω}, there was a one to one correspondence between accepting runs of M on σ and accepting runs of M_{1} on σ. □

Then one can set the following definition:

Definition 5.12 For all k ∈ ℕ ∪ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}, let

CF L_{ω}(α ≤ k) = {L(M) | M ∈ BP DA(α ≤ k)} = {L(M) | M ∈ MP DA(α ≤ k)}

CF L_{ω}(α < k) = {L(M) | M ∈ BP DA(α < k)} = {L(M) | M ∈ MP DA(α < k)}

For every k, being an integer ≥ 2 or in {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}, a context free ωlanguage L is said to be inherently ambiguous of degree k, if

L ∈ A(k) − CF L_{ω} = CF L_{ω}(α ≤ k) − CF L_{ω}(α < k)

Remark 5.13 As in the finitary case, for a BPDA or MPDA M accepting infinite words over the alphabet Σ, α_{M} is equal to zero if and only if L(M) is the empty set because in that case α_{M}(x) = 0 for all x ∈ Σ^{ω}.

Remark 5.14 For k = 2^{ℵ_{0}} the class CF L(α ≤ 2^{ℵ_{0}}) is the whole class CF L_{ω}. For k = 1, the class CF L_{ω}(α ≤ 1) is the class of non ambiguous context free ω-languages.

We shall now extend Theorem 3.11:

Theorem 5.15 For all k ∈ ℕ ∪ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}, The classes CF L_{ω}(α ≤ k) and CF L_{ω}(α < k) are closed under intersection with ω-regular languages.

Proof. We use the same construction as in the proof of Theorem 3.11. Let L = L(M) be an ω-CFL in the class CF L_{ω}(α ≤ k) (respectively CF L_{ω}(α < k)) accepted by a MPDA M = (K, Σ, Γ, δ, q_{0}, Z_{0}, F) in MP DA(α ≤ k) (respectively MP DA(α < k)) and L′ = L(M′) be an ω-regular language accepted by a deterministic MA M′ = (K′, Σ, δ′, q′_{0}, F′).

The ω-language L∩L′ is accepted by a MPDA M′′ which is the classical product of the two machines M and M′ with appropriate acceptance conditions, formally written in the above proof.

It is clear that M′′ is in MP DA(α ≤ k) (respectively MP DA(α < k)), because each accepting run of M′′ on a word σ ∈ L(M′′) is derived from an accepting run of M on σ in a unique way. □

Considering closure under union we shall prove the following result:

Theorem 5.16 (a) For all k ∈ ℕ ∪ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}, the classes CF L_{ω}(α ≤ k)

and CF L_{ω}(α < k) are closed under disjoint finite union.

(b) For all k ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}, the classes CF L_{ω}(α ≤ k) and CF L_{ω}(α < k) are closed under finite union.

(c) Let k_{1}, …, k_{n} be some positive integers and for all i ∈ [1, n] let L_{i} ∈ CF L_{ω}(α ≤ k_{i}), then

⋃_{1≤i≤n} L_{i} ∈ CF L_{ω}(α ≤ (k_{1} + k_{2} + … + k_{n}))

Proof. In order to prove (a), we can make a similar construction as in the proof of proposition 3.15.

The same construction implies (b) because a finite union of finite sets is a finite set, a finite union of countable sets is a countable set, and a finite union of sets of cardinal ≤ 2^{ℵ_{0}} is a set of cardinal ≤ 2^{ℵ_{0}}.

(c) follows easily from the above construction of a BPDA M accepting ⋃_{1≤i≤n} L_{i} from BPDA M_{i} accepting L_{i}. □

We can now study first some links between the case of finite words and the infinitary case.

Proposition 5.17 Let V ⊆ Σ^{⋆} be a finitary context free language over the alphabet Σ and d be a new letter not in Σ, then the following equivalences hold for all k ∈ ℕ ∪ {ℵ_{0}^{−}}:

(a) V.d^{ω} is in CF L_{ω}(α ≤ k) iff V is in CF L(α ≤ k).

(b) V.d.(Σ ∪ {d})^{ω} is in CF L_{ω}(α ≤ k) iff V is in CF L(α ≤ k).

Proof. (a) Return now to the proof of Proposition 3.12. Let V ⊆ Σ^{⋆} be a finitary context free language in CF L(α ≤ k), for k ∈ ℕ ∪ {ℵ_{0}^{−}}. We have constructed from a PDA accepting V a BPDA accepting V.d^{ω}. This construction preserved non ambiguity and it is easy to see that it preserves also the degrees of ambiguity and that V.d^{ω} ∈ CF L_{ω}(α ≤ k).

Conversely by the Remark 3.13, the inverse construction implies that V is in CF L(α ≤ k) if V.d^{ω} is in CF L_{ω}(α ≤ k).

(b) Assume first that V is in CF L(α ≤ k). As for (a), an easy construction shows that V.d.(Σ ∪ {d})^{ω} is in CF L_{ω}(α ≤ k).

Conversely assume that V.d.(Σ ∪ {d})^{ω} is in CF L_{ω}(α ≤ k). Then the class CF L_{ω}(α ≤ k) being closed under intersection with ω-regular languages, the ω-language

V.d^{ω} = V.d.(Σ ∪ {d})^{ω} ∩ Σ^{⋆}.d^{ω}

is in the class CF L_{ω}(α ≤ k) and then the proof of (a) shows that V is in CF L(α ≤ k). □

Example 5.18 We have now first examples of ω-CFL which are inherently ambiguous of degree k, for k ≥ 2 and k ∈ ℕ ∪ {ℵ_{0}^{−}}. We have seen in Example 5.6 that if k is an integer ≥ 2 and

A_{k} = ⋃_{i=1}^{k}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}} … a_{2k−1}^{n_{k}}a_{2k}^{n_{k}} | n_{1}, …, n_{k} ≥ 1}

A_{∞} = A_{2}^{⋆}

Then A_{k} is inherently ambiguous of degree k over the alphabet Σ_{k} = {a_{1}, … a_{2k}} and A_{∞} is inherently ambiguous of infinite degree over the alphabet Σ_{2}. Then if d is a new letter the ω-languages A_{k}.d^{ω} and A_{k}.d.(Σ ∪ {d})^{ω} are ω-CFL which are inherently ambiguous of degree k, and A_{∞}.d^{ω} and A_{∞}.d.(Σ ∪ {d})^{ω} are inherently ambiguous of degree ℵ_{0}^{−}.

Remark 5.19 Using these examples one can prove that, for each integer k ≥ 1, the class CF L_{ω}(α ≤ k) is not closed under finite union, as we have already proved that the class NA − CF L_{ω} = CF L_{ω}(α ≤ 1) is not closed under finite union (see proposition 3.15).

It is natural to ask now whether there exist some ω-CFL which are inherently ambiguous of degree ℵ_{0} or 2^{ℵ_{0}}. We first give examples of ω-CFL in the class A(ℵ_{0}) − CF L_{ω} and next in the class A(2^{ℵ_{0}}) − CF L_{ω}.

Example 5.20 For an integer n ≥ 0 let n̄ = ba^{n} be the unary representation of n over the alphabet Σ = {a, b}. Then the following context free ω-languages G′_{1}, G′_{≠}, G′_{<}, G′_{>}, G′_{=} are inherently ambiguous of degree ℵ_{0}, where:

G′_{1} = {n̄_{1}n̄_{2} … n̄_{p} … | n_{j} = n_{1} holds for some j ≥ 2}
G′_{≠} = {n̄_{1}n̄_{2} … n̄_{p} … | for some j n_{j} ≠ j}
G′_{<} = {n̄_{1}n̄_{2} … n̄_{p} … | for some j n_{j} < j}
G′_{>} = {n̄_{1}n̄_{2} … n̄_{p} … | for some j n_{j} > j}
G′_{=} = {n̄_{1}n̄_{2} … n̄_{p} … | for some j n_{j} = j}

(where the variable p runs over all integers ≥ 1 and the n_{j} over integers ≥ 0.)

It is easy to see that each of the above ω-languages is in the class CF L_{ω}(α ≤ ℵ_{0}) by finding a BPDA in BP DA(α ≤ ℵ_{0}) accepting it. Explain for example the behaviour of such a BPDA M accepting G′_{=}. The pushdown store of M is used like a counter. The counter is increased of one when a letter b is read until the BPDA M, after reading the j^{th} letter b, decreases the counter of one for each letter a read. If then the counter value is zero and the following letter is a b the BP DA works like a deterministic BA and just checks that there is infinitely many letters b in the ω-word. Then the non determinism has been used to guess the integer j. And in an ω-word n̄_{1}n̄_{2} … n̄_{p} … such that for some j, n_{j} = j, there exist only countably many such choices. Thus an ω-word σ ∈ G′_{=} has only countably many accepting runs by the BPDA M and G′_{=} ∈ CF L_{ω}(α ≤ ℵ_{0}).

In a similar manner a BPDA M_{1} accepting G′_{1} need only a counter as a pushdown store. The machine M_{1}, when reading an ω-word n̄_{1}n̄_{2} … n̄_{p} … has to keep the integer n_{1} in the memory of the stack and then it guesses, using the non determinism, an integer j ≥ 2 and checks that n_{j} = n_{1}. We can see that for a given ω-word σ ∈ G′_{1}, there are only countably such choices, hence σ ∈ G′_{1} has only countably many accepting runs by the BPDA M_{1} and G′_{1} ∈ CF L_{ω}(α ≤ ℵ_{0}).

In order to prove that G′_{1} is not in CF L_{ω}(α < ℵ_{0}), we will use in [Fin00d] an extension of Ogden’s Lemma which has been already often used to prove the inherent ambiguity of some context free finitary languages, [Her97].

Example 5.21 Let as above

V_{1} = {a^{n}b^{m}c^{p} | n, m, p are integers ≥ 1 and n = m}
V_{2} = {a^{n}b^{m}c^{p} | n, m, p are integers ≥ 1 and m = p}

The languages V_{1} and V_{2} are deterministic context free, i.e. that there are accepted by some deterministic pushdown automata, hence they are non ambiguous context free languages. But their union V = V_{1} ∪ V_{2} is an inherently ambiguous context free language, [Mau69]. And the context free ω-language V^{ω} is in A(2^{ℵ_{0}}) − CF L_{ω}.

As for the preceding example, we will show this result, using Ogden’ s Lemma, in another paper [Fin00d].

Some other examples of context free ω-languages of maximum degree of ambiguity, i.e. of degree 2^{ℵ_{0}}, will be given in next section using topological properties of ω-CFL (see example 6.3 below). We strongly conjecture that some other examples may be provided by the following Conjecture 5.22 Let V ⊆ Σ^{⋆} be a finitary context free language over the alphabet Σ and d be a new letter not in Σ, then the following equivalence holds:

(V.d)^{ω} is in A(2^{ℵ_{0}}) − CF L_{ω} iff V is in A − CF L

Remark that the following proposition is easy to prove:

Proposition 5.23 Let V ⊆ Σ^{⋆} be a finitary context free language over the alphabet Σ and d be a new letter not in Σ, then the following equivalence holds:

(V.d)^{ω} is in NA − CF L_{ω} iff V is in NA − CF L

Proof. If V is in NA−CF L one can easily construct a non ambiguous BPDA M accepting (V.d)^{ω}. Assume now that (V.d)^{ω} is in NA−CF L_{ω} and let u ∈ V. Then the ω-language

V.(d.u)^{ω} = (V.d)^{ω} ∩ Σ^{⋆}.(d.u)^{ω}

is also in NA − CF L_{ω} because this class is closed under intersection with ω-regular languages. But then with a similar argument as in the proof of proposition 3.12 one can find a non ambiguous PDA accepting the finitary language V thus V is in NA − CF L. □

6 Topological properties

6.1 Recall of previous results

When considering regular or context free ω-languages, natural questions arise: are they all Borel sets of finite rank, Borel sets, analytic sets … ?

Landweber studied first the topological properties of ω-regular languages. McNaughton’s Theorem implies that ω-regular languages are boolean combination of G_{δ} sets, [MaN66]. Landweber characterized the ω-regular languages in each of the Borel classes F, G, F_{σ}, G_{δ}, and showed that one can decide, for an effectively given ω-regular language L, whether L is in F, G, F_{σ}, or G_{δ}. It turned out that an ω-regular language is in the class G_{δ} iff it is accepted by a DBA. These results were extended to deterministic ω-CFL by Linna [Lin77]. In the non deterministic case, Cohen and Gold proved in [CG78] that one cannot decide whether an ω-CFL is in the class F, G or G_{δ}. We proved in [Fin01a] that there are ω-CFL in each Borel class of finite rank. And that, for any Borel class Σ_{n}^{0} or Π_{n}^{0}, n being an integer, one cannot decide whether an ω-CFL is in Σ_{n}^{0} or Π_{n}^{0}. Every ω-CFL is an analytic set but we showed in [Fin00a] that there exist some ω-CFL which are analytic but non Borel sets.

One may ask for a similar investigation for the subclasses of CF L_{ω} defined above by means of the notion of ambiguity.

From a general study of topological properties of transition systems due to Arnold [Arn83a] we know that every non ambiguous ω-CFL is a Borel set (one considers a BPDA as a transition system with infinitely many states). Pierre Simonnet, using a uniformization theorem of descriptive set theory, has extended this result by proving the following Theorem:

Theorem 6.1 (Simonnet [Sim00]) Let L(M) be an ω-CFL accepted by a BPDA M such that L(M) is an analytic but non Borel set. Then there exist 2^{ℵ_{0}} ω-words, each of which having 2^{ℵ_{0}} accepting runs by M.

With our notations we can infer from this result the following one:

Corollary 6.2 Let L ⊆ Σ^{ω} be an ω-CFL. If L is non ambiguous or inherently ambiguous of degree k, with k an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}}, then L is a Borel subset of Σ^{ω}.

Example 6.3 Recall here the construction of a simple context free ω-language which is analytic but not Borel, [Fin00a]. Let Σ = {0, 1} be an alphabet containing two letters 0 and 1, A be a new letter and

D = {u.A.v / u, v ∈ Σ^{⋆} and (|v| = 2|u|) or (|v| = 2|u| + 1) }

Then D is a context free language over the alphabet (Σ ∪ {A}). Let then g be the substitution Σ → P ((Σ ∪ {A})^{⋆}) defined by a → a.D.

Let then W = 0^{⋆}.1. The image of W by the substitution g is g(W) which is a finitary context free language such that (g(W))^{ω} is an analytic but non Borel context free ω-language.

Thus Simonnet’s Theorem implies that

(g(W))^{ω} ∈ A(2^{ℵ_{0}}) − CF L_{ω}

Recall that we have proved in proposition 3.16 that one cannot decide whether an arbitrary ω-CFL L is non ambiguous, i.e. whether L ∈ CF L_{ω}(α ≤ 1). We can now extend this result by proving the following Theorem:

Theorem 6.4 Let k be an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}}. Then it is undecidable to determine whether an arbitrary ω-CFL is in the class CF L_{ω}(α ≤ k) (respectively CF L_{ω}(α < k)). So one cannot decide whether an arbitrary ω-CFL is inherently ambiguous of degree 2^{ℵ_{0}}.

Proof. Recall that we proved in [Fin00a] that one cannot decide whether an arbitrary ω-CFL is a Borel set. In fact we found a family of ω-CFL D(X, Y) over a finite alphabet Σ_{A} such that only two cases may happen. In the first case, D(X, Y) = (Σ_{A})^{ω}, therefore D(X, Y) is an ω-regular language and it is a non ambiguous ω-CFL hence D(X, Y) ∈ CF L_{ω}(α ≤ 1) and D(X, Y) ∈ CF L_{ω}(α ≤ k) hold for every integer k ≥ 2 and for k ∈ {ℵ_{0}^{−}, ℵ_{0}}.

In the second case D(X, Y) is a Σ_{1}^{1}-complete subset of (Σ_{A})^{ω}, and then by Theorem 6.1, D(X, Y) ∈ A(2^{ℵ_{0}}) − CF L_{ω} holds and D(X, Y) is not in any class CF L_{ω}(α ≤ k) or CF L_{ω}(α < k) for k an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}}.

But one cannot decide which case holds and this ends the proof. □

From now on, we shall pursue the study of links between topological properties and ambiguity of ω-CFL .

We have previously proved that the class of context free ω-languages exhausts the finite ranks of the Borel hierarchy (it meets every finite level of the Borel hierarchy), using previous results of Duparc on the Wadge hierarchy of Borel sets. We shall see that these results will be still useful in the present context. Hence we introduce now the Wadge Hierarchy which is a great refinement of the Borel hierarchy:

6.2 Wadge hierarchy

Definition 6.5 For E ⊆ X^{ω} and F ⊆ Y^{ω}, E is said Wadge reducible to F (E ≤_{W} F) iff there exists a continuous function f : X^{ω} → Y^{ω}, such that E = f^{−1}(F). E and F are Wadge equivalent iff E ≤_{W} F and F ≤_{W} E. this will be denoted by E ≡_{W} F. And we shall say that E <_{W} F iff E ≤_{W} F but not F ≤_{W} E.

The relation ≤_{W} is reflexive and transitive, and ≡_{W} is an equivalence relation. The equivalence classes of ≡_{W} are called Wadge degrees. A set E ⊆ X^{ω} is said to be selfdual iff E ≡_{W} E^{−}; otherwise E is said to be non selfdual. W H is the class of Borel subsets of a set X^{ω}, where X is a finite set, equipped with ≤_{W} and with ≡_{W}. For E ⊆ X^{ω} and F ⊆ Y^{ω}, if E ≤_{W} F and E = f^{−1}(F) where f is a continuous function from X^{ω} into Y^{ω}, then f is called a continuous reduction of E to F. Intuitively it means that E is less complicated than F because to check whether x ∈ E it suffices to check whether f(x) ∈ F where f is a continuous function. Hence the Wadge degree of an ω-language is a measure of its topological complexity.

Remark 6.6 In the above definition, we consider that a subset E ⊆ X^{ω} is given together with the alphabet X.

Then we can define the Wadge class of a set F:

Definition 6.7 Let F be a Borel subset of X^{ω}. The wadge class of F is [F] defined by: [F] = {E | E ⊆ Y^{ω} for a finite alphabet Y and E ≤_{W} F }.

Recall that each Borel class Σ_{n}^{0} and Π_{n}^{0} is a Wadge class.

Recall now that a set X is well ordered by a binary relation < iff < is a linear order on X and there is not any strictly decreasing (for <) infinite sequence of elements in X.

Theorem 6.8 (Wadge) Up to the complement and ≡_{W}, the class of Borel subsets of X^{ω}, for X a finite alphabet, is a well ordered hierarchy. There is an ordinal |W H|, called the length of the hierarchy, and a map d_{W}^{0} from W H onto |W H|, such that for all A, B ∈ W H: d_{W}^{0} A < d_{W}^{0} B ↔ A <_{W} B and d_{W}^{0} A = d_{W}^{0} B ↔ [A ≡_{W} B or A ≡_{W} B^{−}].

If we restrict the study to Borel sets of finite rank, the Wadge hierarchy has then length ^{1}ϵ_{0} where ^{1}ϵ_{0} is the limit of the ordinals ω_{1}(n) defined by ω_{1}(1) = ω_{1} and ω_{1}(n + 1) = ω_{1}^{ω_{1}(n)} for n a non negative integer, ω_{1} being the first non countable ordinal. The length of the whole Wadge hierarchy of Borel sets is a much larger ordinal. It is described using Veblen functions in [Wad84] [Dup01].

Wadge gave first a description of the Wadge hierarchy of Borel sets, [Wad84]. Duparc recently got a new proof of Wadge’s results and he gave a normal form of Borel sets, i.e. an inductive construction of a Borel set of every given degree [Dup95a] [Dup01]. His proof relies on set theoretic operations which are the counterpart of arithmetical operations over ordinals needed to compute the Wadge degrees.

In fact Duparc studied the Wadge hierarchy via the study of the conciliating hierarchy. He introduced in [Dup95a] [Dup01] conciliating sets which are sets of finite or infinite words over an alphabet X, i.e. subsets of X^{⋆}∪X^{ω} = X^{≤ω}. It turned out that the conciliating hierarchy is isomorphic to the Wadge hierarchy of non self dual Borel sets, via the following correspondence:

For A ⊆ X^{≤ω} and d a letter not in X, define

A^{d} = {x ∈ (X ∪ {d})^{ω} / x(/d) ∈ A}

where x(/d) is the sequence obtained from x when removing every occurrence of the letter d.

Considering conciliating sets, we shall sometimes simply say ”A is a Borel set” instead of ”A^{d} is a Borel set”. In the same way we shall say ”A is in the Borel class Σ_{α}^{0} (respectively Π_{α}^{0})” instead of ”A^{d} is in the Borel class Σ_{α}^{0} (respectively Π_{α}^{0})”.

The set theoretic operations are then defined over conciliating sets. We shall use in this paper the operation of exponentiation.

6.3 Operation of exponentiation of conciliating sets

We first recall the following:

Definition 6.9 Let X_{A} be a finite alphabet and ↞∉ X_{A}, let X = X_{A} ∪ {↞}. Let x be a finite or infinite word over the alphabet X = X_{A} ∪ {↞}. Then x^{↞} is inductively defined by: λ^{↞} = λ, For a finite word u ∈ (X_{A} ∪ {↞})^{⋆}: (u.a)^{↞} = u^{↞}.a, if a ∈ X_{A}, (u. ↞)^{↞} = u^{↞} with its last letter removed if |u^{↞}| > 0, (u. ↞)^{↞} = λ if |u^{↞}| = 0, and for u infinite: (u)^{↞} = lim_{n∈ω}(u[n])^{↞}, where, given β_{n} and v in X_{A}^{⋆}, v ⊑ lim_{n∈ω} β_{n} ↔ ∃n∀p ≥ n β_{p}[|v|] = v.

Remark 6.10 For x ∈ X^{≤ω}, x^{↞} denotes the string x, once every ↞ occuring in x has been ”evaluated” to the back space operation (the one familiar to your computer!), proceeding from left to right inside x. In other words x^{↞} = x from which every interval of the form ”a ↞ ” (a ∈ X_{A}) is removed. So we may consider the letter ↞ as an eraser.

For example if u = (a ↞)^{n}, for n ≥ 1, u = (a ↞)^{ω} or u = (a ↞↞)^{ω} then (u)^{↞} = λ, if u = (ab ↞)^{ω} then (u)^{↞} = a^{ω}, if u = bb(↞ a)^{ω} then (u)^{↞} = b.

We can now define the operation A → A^{∼} of exponentiation of conciliating sets:

Definition 6.11 For A ⊆ X_{A}^{≤ω} and ↞ ∉ X_{A}, let X = X_{A} ∪ {↞} and A^{∼} = {x ∈ (X_{A} ∪ {↞})^{≤ω} | x^{↞} ∈ A}.

The operation ∼ is monotone with regard to the Wadge ordering and produce some sets of higher complexity, in the following sense:

Theorem 6.12 (Duparc [Dup01] )a) For A ⊆ X_{A}^{≤ω} and B ⊆ X_{B}^{≤ω}, A^{d}

and B^{d} borel sets, A^{d} ≤_{W} B^{d} ↔ (A^{∼})^{d} ≤_{W} (B^{∼})^{d}.

b) If A^{d} ⊆ (X_{A} ∪ {d})^{ω} is a Σ_{n}^{0}-complete (respectively Π_{n}^{0}-complete) set ( for an integer n ≥ 1 ), then (A^{∼})^{d} is a Σ_{n+1}^{0}-complete (respectively Π_{n+1}^{0}- complete) set.

We proved in [Fin01a] that the class CF L_{ω} is closed under this operation ∼.

Theorem 6.13 Whenever A ⊆ X_{A}^{ω} is an ω-CFL, then A^{∼} ⊆ (X_{A} ∪ {↞})^{ω} is an ω-CFL.

We shall now extend this result by proving the following:

Theorem 6.14 (I) A ⊆ X_{A}^{ω} is in NA − CF L_{ω} if and only if

A^{∼} ⊆ (X_{A} ∪ {↞})^{ω} is in NA − CF L_{ω}. (II) A ⊆ X_{A}^{ω} is inherently ambiguous of degree k, where k is an integer ≥ 2

or k ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}} if and only if A^{∼} ⊆ (X_{A} ∪ {↞})^{ω} is inherently ambiguous of the same degree k.

Proof. We reason firstly as in the proof of Theorem 6.13 in [Fin01a]. Let A be an ω-CFL which is accepted by a Büchi pushdown automaton M = (K, X_{A}, Γ, δ, q_{0}, Z_{0}, F).

An ω-word σ ∈ A^{∼} may be considered as an ω-word σ^{↞} ∈ A to which we possibly add, before the first letter σ^{↞}(1) of σ^{↞} (respectively between two consecutive letters σ^{↞}(n) and σ^{↞}(n + 1) of σ^{↞}), a finite word v_{1} (respectively v_{n+1} ) where: v_{n+1} belongs to the context free (finitary) language L_{3} generated by the context free grammar with the following production rules: S → aS ↞ S with a ∈ X_{A}, S → a ↞ S with a ∈ X_{A}, S → λ (λ being the empty word). this language L_{3} corresponds to words where every letter of X_{A} has been removed after using the back space operation. And v_{1} belongs to the finitary language L_{4} = (↞)^{⋆}.(L_{3}.(↞)^{⋆})^{⋆}. This language corresponds to words where every letter of X_{A} has been removed after using the back space operation and this operation maybe has been used also when there was not any letter to erase. L_{4} is a context free language because the class CF L is closed under star operation and concatenation product.

Remark 6.15 Recall that a one counter automaton is a pushdown automaton with a pushdown alphabet in the form Γ = {Z_{0}, z} where Z_{0} is the bottom symbol and always remains at the bottom of the pushdown store. And a one counter language is a (finitary) language which is accepted by a one counter automaton by final states. It is easy to see that in fact L_{3} and L_{4} are deterministic one-counter languages, i.e. L_{3} and L_{4} are accepted by deterministic one-counter automata. And for a ∈ X_{A}, the language L_{3}.a is also accepted by a deterministic one-counter automaton.

Then we shall construct from M another BPDA M^{∼} which accepts the ωlanguage A^{∼} over the alphabet X = X_{A} ∪ {↞}. Describe first informally the behaviour of the machine M^{∼} when it reads an ωword σ ∈ A^{∼}. Recall that this word may be considered as an ω-word σ^{↞} ∈ A to which we possibly add, before the first letter σ^{↞}(1) of σ^{↞} (respectively between two consecutive letters σ^{↞}(n) and σ^{↞}(n + 1) of σ^{↞}), a finite word v_{1} (respectively v_{n+1} ) where v_{1} belongs to the context free language L_{4} and v_{n+1} belongs to the context free language L_{3}.

M^{∼} starts the reading as a pushdown automaton accepting the language L_{4}. Then M^{∼} begins to read as M, but at any moment of the computation it may guess (using the non determinism) that it reads a finite segment v of L_{3} which will be erased (using the eraser ↞). It reads v using an additional stack letter E which permits to simulate a one counter automaton at the top of the stack while keeping the memory of the stack of M. Then, after the reading of v, M^{∼} simulates again the machine M and so on.

More formally M^{∼} = (K^{∼}, X_{A} ∪ {↞}, Γ ∪ {E}, δ^{∼}, q′_{0}, Z_{0}, F), where

K^{∼} = K ∪ {q′_{0}} ∪ {q^{1} | q ∈ K}

E is a new letter not in Γ,

And the transition relation δ^{∼} is defined by the following cases (where the transition rules (a)-(d) are used to simulate a pushdown automaton accepting L_{4} and the BPDA M^{∼} enters in a state q^{1}, for q ∈ K, when it simulates a one counter automaton accepting L_{3}):

(a) δ^{∼}(q′_{0}, ↞, Z_{0}) = (q′_{0}, Z_{0}).

(b) (q′_{0}, EZ_{0}) ∈ δ^{∼}(q′_{0}, a, Z_{0}), for each a ∈ X_{A}.

(c) δ^{∼}(q′_{0}, ↞, E) = (q′_{0}, λ).

(d) δ^{∼}(q′_{0}, a, E) = (q′_{0}, EE), for each a ∈ X_{A}.

(e) (q, ν) ∈ δ^{∼}(q′_{0}, a, Z_{0}) iff (q, ν) ∈ δ(q_{0}, a, Z_{0}), for each a ∈ X_{A} ∪ {λ} and ν ∈ Γ^{⋆} and q ∈ K.

(f) (q′, ν) ∈ δ^{∼}(q, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} ∪ {λ} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(g) (q^{1}, Eγ) ∈ δ^{∼}(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(h) δ^{∼}(q^{1}, a, E) = (q^{1}, EE), for each a ∈ X_{A} and q ∈ K.

(i) δ^{∼}(q^{1}, ↞, E) = (q^{1}, λ).

(j) (q′, ν) ∈ δ^{∼}(q^{1}, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(k) (q^{1}, Eγ) ∈ δ^{∼}(q^{1}, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(I) We claim now that if M is a non ambiguous BPDA then M^{∼} is also a non ambiguous BPDA. This comes from the fact that the operation of erasing in an ω-word σ ∈ A^{∼} is uniquely determined. Moreover the λ-transitions occurring in the reading of σ by M^{∼} simulate the λ-transitions occurring in the reading of σ^{↞} by M and they can not appear from a state of K^{1} (transition rule (j)). Hence they may appear just before but not just after the reading of a segment v which will be erased. This ensures that the accepting run of an ω-word σ ∈ A^{∼} is unique. And in an ω-word σ accepted by M^{∼} there exist infinitely many letters of X_{A} which induce an infinite word σ^{↞} of (X_{A})^{ω} which is in A (because otherwise at some moment M^{∼} would enter in a state of K^{1} and then remain in states of K^{1}).

This proves that if A is in NA − CF L_{ω} then A^{∼} is in NA − CF L_{ω}.

Conversely assume that A^{∼} is in NA − CF L_{ω}. Then there exists a non ambiguous BPDA N which accepts the ω-language A^{∼}. But it is easy to see that

A^{∼} ∩ (X_{A})^{ω} = A

Hence one can get a BPDA M accepting A from the BPDA N by suppressing the transition rules involving the input letter ↞. Each accepting run of M on an ω-word σ ∈ A comes from an accepting run of N on σ. Thus M is non ambiguous because N was non ambiguous. And A = L(M) is in NA − CF L_{ω}.

(II) Assume now that A ⊆ X_{A}^{ω} is inherently ambiguous of degree k, where k is an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}. Let then M ∈ BP DA(α ≤ k) accepting A. For the same reasons as for (I) above, M^{∼} ∈ BP DA(α ≤ k) holds. Thus A^{∼} ∈ CF L_{ω}(α ≤ k). Now if A^{∼} ∈ CF L_{ω}(α < k) we could construct, from a BPDA N ∈ BP DA(α < k) accepting A^{∼}, another BPDA M′ accepting A by suppressing the transition rules involving the input letter ↞. And then M′ would be in BP DA(α < k). This would lead to a contradiction thus A^{∼} ∉ CF L_{ω}(α < k) and A^{∼} ∈ A(k) − CF L_{ω}.

Assume conversely that A^{∼} ∈ A(k) − CF L_{ω}, where k is an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}.

Let M be a BPDA in BP DA(α ≤ k) accepting A^{∼}. Like above we can construct from M, by suppressing the transition rules involving the input letter ↞, another BPDA N in BP DA(α ≤ k) accepting A. Thus A ∈ CF L_{ω}(α ≤ k).

And if A ∈ CF L_{ω}(α < k) held, the BPDA M^{∼} accepting A^{∼} we have constructed above would be in BP DA(α < k). This is impossible because A^{∼} ∈ A(k) − CF L_{ω}. Then A ∉ CF L_{ω}(α < k) and finally A ∈ A(k) − CF L_{ω}.

□

We have just considered above the case of a conciliating set containing only infinite words. We are going to consider the case of a conciliating set containing only finite words.

Theorem 6.16 (I) A ⊆ X_{A}^{⋆} is in NA − CF L if and only if A^{∼} ⊆ (X_{A} ∪ {↞})^{≤ω} is the union of a language in NA − CF L and of an ω-language in NA − CF L_{ω}.

(II) A ⊆ X_{A}^{⋆} is in A(k) − CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}, if and only if A^{∼} ⊆ (X_{A} ∪ {↞})^{≤ω} is the union of a context free language in A(k) − CF L and of an ω-language in A(k) − CF L_{ω}.

Proof. Let A ⊆ X_{A}^{⋆} be a context free language. The set A^{∼} is a subset of (X_{A} ∪ {↞})^{≤ω} which is constituted of finite and infinite words. Let h be the substitution: X_{A} → P ((X_{A} ∪ {↞})^{⋆}) defined by a → a.L_{3} where L_{3} is the context free language defined above. Then it is easy to see that the finite words of A^{∼} are obtained by substituting in A the language a.L_{3} for each letter a ∈ X_{A} and concatenating on the left by the language L_{4}. But CF L is closed under substitution and concatenation [Ber79], then this language is a context free finitary language D_{A}.

The infinite words in A^{∼} constitutes the ω-language D_{A}.(L_{3} − {λ})^{ω} if λ ∉ A, and D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∪ (L_{4} − {λ})^{ω} if λ ∈ A,

The languages L_{4} − {λ} and L_{3} − {λ} are context free, thus the set of infinite words in A^{∼} is an ω-CFL D′_{A} because ω − KC(CF L) ⊆ CF L_{ω} by Theorem 2.11.

With similar ideas as in the preceding case of a conciliating set A containing only infinite words, we shall construct a PDA accepting D_{A} and a MPDA accepting D′_{A}.

Let then A ⊆ X_{A}^{⋆} be a context free language which is accepted by the PDA M = (K, X_{A}, Γ, δ, q_{0}, Z_{0}, (F, Γ)) by final states and topmost stack letters, where F is the set of final states (remark that the accepting condition is just by final states and nonempty storage). And let M_{1}^{∼} be the PDA

M_{1}^{∼} = (K_{1}^{∼}, X_{A} ∪ {↞}, Γ ∪ {E}, δ_{1}^{∼}, q′_{0}, Z_{0}, (F ∪ {q_{F} }, Γ))

where

K_{1}^{∼} = K ∪ {q_{1} | q ∈ K} ∪ {q′_{0}} ∪ {q_{F} }

q_{F} and q′_{0} are new states not in K ∪ {q_{1} | q ∈ K}, E is a new letter not in Γ,

and the transition relation δ_{1}^{∼} is defined by the following cases (where the transition rules (a)-(d) are used to simulate a pushdown automaton accepting L_{4} and the PDA M_{1}^{∼} enters in a state q_{1}, for q ∈ K, when it simulates a one counter automaton accepting L_{3}):

(a) δ_{1}^{∼}(q′_{0}, ↞, Z_{0}) = (q′_{0}, Z_{0}).

(b) (q′_{0}, EZ_{0}) ∈ δ_{1}^{∼}(q′_{0}, a, Z_{0}), for each a ∈ X_{A}.

(c) δ_{1}^{∼}(q′_{0}, ↞, E) = (q′_{0}, λ).

(d) δ_{1}^{∼}(q′_{0}, a, E) = (q′_{0}, EE), for each a ∈ X_{A}.

(e) (q, ν) ∈ δ_{1}^{∼}(q′_{0}, a, Z_{0}) iff (q, ν) ∈ δ(q_{0}, a, Z_{0}), for each a ∈ X_{A} ∪ {λ} and ν ∈ Γ^{⋆} and q ∈ K.

(f) (q′, ν) ∈ δ_{1}^{∼}(q, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} ∪ {λ} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(g) (q_{1}, Eγ) ∈ δ_{1}^{∼}(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(h) δ_{1}^{∼}(q_{1}, a, E) = (q_{1}, EE), for each a ∈ X_{A} and q ∈ K.

(i) δ_{1}^{∼}(q_{1}, ↞, E) = (q_{1}, λ).

(j) (q′, ν) ∈ δ_{1}^{∼}(q_{1}, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(k) (q_{1}, Eγ) ∈ δ_{1}^{∼}(q_{1}, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(l) (q_{F} , γ) ∈ δ_{1}^{∼}(q_{1}, λ, γ) for each γ ∈ Γ and q ∈ F .

The transition rules of M_{1}^{∼} are similar to those of the BPDA M^{∼} of the preceding proof, except for the last transition rule [(l)] which is used to accept words with a final segment v ∈ L_{3} which will be erased using the eraser ↞. We have used a PDA accepting by final states and topmost stack letters because we wanted to be able to continue the computation on such a segment and then we had to avoid a final configuration with empty storage after the reading of a word in A.

By construction L(M_{1}^{∼}) = D_{A} holds.

We are going to prove now the parts of (I) and (II) involving the language D_{A}.

Assume now that A is in NA − CF L. For the same reasons as in the proof of Theorem 6.14 the language D_{A} is in NA − CF L (we shall show below that D′_{A} is in NA − CF L_{ω}). Conversely assume that D_{A} is in NA − CF L then one can construct, from a non ambiguous PDA accepting D_{A}, a non ambiguous PDA accepting A because D_{A} ∩ X_{A}^{⋆} = A; hence A is in NA − CF L.

Assume that A is in A(k) − CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}. Then if M is a PDA in P DA(α ≤ k) accepting A by final states and topmost stack letters, the PDA M_{1}^{∼} we have constructed is in P DA(α ≤ k) hence D_{A} is in CF L(α ≤ k). But if D_{A} was in CF L(α < k), the language A = D_{A} ∩ X_{A}^{⋆} would be in CF L(α < k) because this class is closed under intersection with regular languages and X_{A}^{⋆} is regular. Thus D_{A} is not in CF L(α < k), and D_{A} ∈ A(k) − CF L. (We shall show below that D′_{A} is in A(k) − CF L_{ω}).

Conversely assume that D_{A} ∈ A(k) − CF L. Then A = D_{A} ∩ X_{A}^{⋆} is a context free language in CF L(α ≤ k) because the class CF L(α ≤ k) is closed under intersection with regular languages. If A was in CF L(α < k), the above construction of M_{1}^{∼} would provide, from a PDA M in P DA(α < k) accepting A by final states and topmost stack letters, another PDA in P DA(α < k) accepting D_{A}. This is impossible because D_{A} ∈ A(k) − CF L, therefore

A ∈ A(k) − CF L = CF L(α ≤ k) − CF L(α < k)

Return now to the ω-language D′_{A} which is D_{A}.(L_{3} − {λ})^{ω} if λ ∉ A, and D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∪ (L_{4} − {λ})^{ω} if λ ∈ A.

Consider firstly the case where λ ∉ A and D′_{A} = D_{A}.(L_{3} − {λ})^{ω} and assume again that A ⊆ X_{A}^{⋆} is a context free language which is accepted by the PDA M = (K, X_{A}, Γ, δ, q_{0}, Z_{0}, (F, Γ)) by final states and topmost stack letters, where F is the set of final states. We shall construct, from the PDA M, a MPDA M_{2}^{∼} accepting D′_{A}, with similar ideas as above for the construction of M^{∼} and M_{1}^{∼}.

Let M_{2}^{∼} be the MPDA

M_{2}^{∼} = (K_{2}^{∼}, X_{A} ∪ {↞}, Γ ∪ {E}, δ_{2}^{∼}, q′_{0}, Z_{0}, F_{2})

where

K_{2}^{∼} = K ∪ {q_{1} | q ∈ K} ∪ {q_{2} | q ∈ K} ∪ {q′_{0}}
q′_{0} is a new state not in K ∪ {q_{1} | q ∈ K} ∪ {q_{2} | q ∈ K}

E is a new letter not in Γ

F_{2} = {{q_{1}, q_{2}} | q ∈ F }

And the transition relation δ_{2}^{∼} is defined by the following cases (where the transition rules (a)-(d) are used to simulate a pushdown automaton accepting L_{4} and the PDA M_{2}^{∼} enters in a state q_{1}, for q ∈ K, when it simulates a one counter automaton accepting L_{3}):

(a) δ_{2}^{∼}(q′_{0}, ↞, Z_{0}) = (q′_{0}, Z_{0}).

(b) (q′_{0}, EZ_{0}) ∈ δ_{2}^{∼}(q′_{0}, a, Z_{0}), for each a ∈ X_{A}.

(c) δ_{2}^{∼}(q′_{0}, ↞, E) = (q′_{0}, λ).

(d) δ_{2}^{∼}(q′_{0}, a, E) = (q′_{0}, EE), for each a ∈ X_{A}.

(e) (q, ν) ∈ δ_{2}^{∼}(q′_{0}, a, Z_{0}) iff (q, ν) ∈ δ(q_{0}, a, Z_{0}), for each a ∈ X_{A} ∪ {λ} and ν ∈ Γ^{⋆} and q ∈ K.

(f) (q′, ν) ∈ δ_{2}^{∼}(q, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} ∪ {λ} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(g) (q_{1}, Eγ) ∈ δ_{2}^{∼}(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

(h) δ_{2}^{∼}(q_{1}, a, E) = (q_{1}, EE), for each a ∈ X_{A} and q ∈ K.

(i) δ_{2}^{∼}(q_{1}, ↞, E) = (q_{1}, λ).

(j) (q′, ν) ∈ δ_{2}^{∼}(q_{1}, a, γ) iff (q′, ν) ∈ δ(q, a, γ), for each a ∈ X_{A} and γ ∈ Γ and ν ∈ Γ^{⋆} and q, q′ ∈ K.

(k) (q_{2}, γ) ∈ δ_{2}^{∼}(q_{1}, λ, γ) for each γ ∈ Γ and q ∈ K.

(l) (q_{1}, Eγ) ∈ δ_{2}^{∼}(q_{2}, a, γ) for each a ∈ X_{A} and γ ∈ Γ and q ∈ K.

The differences between the transition rules of M_{1}^{∼} and those of M_{2}^{∼} rely on transition rules [(k)] and [(l)]. We have introduced new states q_{2}, for q ∈ K, which are used in λ-transitions and appear during the reading of a segment v = v_{i}.v_{i+1} which is in L_{3}, with v_{i} and v_{i+1} minimal words in L_{3} (i.e. containing none strict initial prefix in L_{3}); such a state q_{2} appears after the reading of the word v_{i} and before the reading of the word v_{i+1}.

By construction L(M_{2}^{∼}) = D′_{A}

Assume now that A is in NA−CF L and that M is a non ambiguous PDA. By construction the MPDA M_{2}^{∼} is non ambiguous and then D′_{A} is non ambiguous.

If we assume that A is in A(k)−CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}, then we can construct M_{2}^{∼} from a PDA in P DA(α ≤ k) accepting A by final states and topmost stack letters, and the resulting MPDA M_{2}^{∼} is in MP DA(α ≤ k). Thus D′_{A} ∈ CF L_{ω}(α ≤ k). If D′_{A} was in CF L_{ω}(α < k), then for a fixed letter b ∈ X_{A}, the ω-language

A.(b. ↞)^{ω} = D′_{A} ∩ X_{A}^{⋆}.(b. ↞)^{ω}

would be in CF L_{ω}(α < k) because the class CF L_{ω}(α < k) is closed under intersection with ω-regular languages and the ω-language X_{A}^{⋆}.(b. ↞)^{ω} is regular.

But then one could construct, from a BPDA in BP DA(α < k) accepting A.(b. ↞)^{ω}, a PDA in P DA(α < k) accepting A (with similar ideas as in the proof of Theorem 3.12). But by hypothesis A is in A(k) − CF L hence A is not in CF L(α < k). Thus D′_{A} is not in CF L_{ω}(α < k) and

D′_{A} ∈ A(k) − CF L_{ω}

Consider now the case where λ ∈ A and

D′_{A} = D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∪ (L_{4} − {λ})^{ω}

It is easy to show that the ω-language (L_{4}−{λ})^{ω} is a non ambiguous context free ω-language. In fact it is accepted by a deterministic BPDA.

Assume now that A ∈ NA − CF L. Then A − {λ} = A ∩ X_{A}^{+} is also a non ambiguous context free language because the class NA − CF L is closed under intersection with regular languages. Then the preceding case shows that

D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∈ NA − CF L_{ω}

We can conclude that D′_{A} ∈ NA − CF L_{ω} because the class NA − CF L_{ω} is closed under disjoint finite union.

Assume now that A ∈ A(k) − CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}. Then it is easy to show that A − {λ} is also in A(k) − CF L. The preceding case shows that

D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∈ A(k) − CF L_{ω}

Hence

D_{(A−{λ})}.(L_{3} − {λ})^{ω} ∈ CF L_{ω}(α ≤ k)

and we can infer that D′_{A} ∈ CF L_{ω}(α ≤ k) because the class CF L_{ω}(α ≤ k) is closed under disjoint finite union.

And if D′_{A} was in CF L_{ω}(α < k), then for a fixed letter b ∈ X_{A}, the ω-language

(A − {λ}).(b. ↞)^{ω} = D′_{A} ∩ X_{A}^{+}.(b. ↞)^{ω}

would be in CF L_{ω}(α < k) because the class CF L_{ω}(α < k) is closed under intersection with ω-regular languages and the ω-language X_{A}^{+}.(b. ↞)^{ω} is regular.

But then one could construct, from a BPDA in BP DA(α < k) accepting (A − {λ}).(b. ↞)^{ω}, a PDA in P DA(α < k) accepting (A − {λ}) (with similar ideas as in the proof of Theorem 3.12). But by hypothesis (A − {λ}) is in A(k) − CF L hence (A − {λ}) is not in CF L(α < k). Thus D′_{A} is not in CF L_{ω}(α < k) and

D′_{A} ∈ A(k) − CF L_{ω}
□

Duparc’s operation of exponentiation is defined over conciliating sets which are sets of finite and infinite words. So we consider now conciliating sets which are unions of a finitary context free language and of a context free ωlanguage. These conciliating sets are infinitary context free languages studied by D. Beauquier in [Bea84a] [Bea84b] and they also appear in the study of processes which may terminate or not.

Let then

L = A ∪ B

where A is a CFL and B is an ω-CFL over the same alphabet X_{A} = X_{B}.

With the preceding notations

L^{∼} = A^{∼} ∪ B^{∼} = D_{A} ∪ D′_{A} ∪ B^{∼}

It is easy to see that this union is disjoint, because

(1) If x ∈ D_{A} then x is a finite word.

(2) If x ∈ D′_{A} then x is an infinite word and x^{↞} is a finite word (in A).

(3) If x ∈ B^{∼} then x is an infinite word and x^{↞} is an infinite word (in B).

The degree of ambiguity of D_{A} is the same as the degree of ambiguity of A by the preceding Theorem. We want now to determine the degree of ambiguity of D′_{A} ∪ B^{∼} which is an ω-CFL over the alphabet X_{A} ∪ {↞}. Let us state the following proposition.

Proposition 6.17 Let L = A ∪ B where A is a CFL and B is an ω-CFL over the same alphabet X_{A} = X_{B}. With the preceding notations the degree of ambiguity of D′_{A} ∪ B^{∼} is given by the following cases:

(1) If A ∈ NA − CF L and B ∈ NA − CF L_{ω} then

(D′_{A} ∪ B^{∼}) ∈ NA − CF L_{ω}

(2) If A ∈ NA − CF L and B ∈ A(k) − CF L_{ω} (with k ≥ 2) then

(D′_{A} ∪ B^{∼}) ∈ A(k) − CF L_{ω}

(3) If A ∈ A(k) − CF L (with k ≥ 2) and B ∈ NA − CF L_{ω} then

(D′_{A} ∪ B^{∼}) ∈ A(k) − CF L_{ω}

(4) If A ∈ A(k) − CF L (with k ≥ 2) and B ∈ A(k′) − CF L_{ω} (with k′ ≥ 2)

then

(D′_{A} ∪ B^{∼}) ∈ A(sup(k, k′)) − CF L_{ω}

Proof. [(1)] Assume that A ∈ NA − CF L and B ∈ NA − CF L_{ω}. By preceding Theorems 6.14 and 6.16, D′_{A} ∈ NA − CF L_{ω} and B^{∼} ∈ NA − CF L_{ω}. Thus

(D′_{A} ∪ B^{∼}) ∈ NA − CF L_{ω}

because the class NA − CF L_{ω} is closed under finite disjoint union and (D′_{A} ∩ B^{∼}) = ∅.

[(2)] Assume that A ∈ NA−CF L and B ∈ A(k)−CF L_{ω} where k is an integer ≥ 2 or k ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}. Then by Theorems 6.14 and 6.16, D′_{A} ∈ NA−CF L_{ω} and B^{∼} ∈ A(k) − CF L_{ω}. Hence D′_{A} and B^{∼} are in CF L_{ω}(α ≤ k) and

(D′_{A} ∪ B^{∼}) ∈ CF L_{ω}(α ≤ k)

because the class CF L_{ω}(α ≤ k) is closed under finite disjoint union.

And if (D′_{A} ∪ B^{∼}) was in the class CF L_{ω}(α < k) then the ω-language

B = (D′_{A} ∪ B^{∼}) ∩ X_{A}^{ω}

would be in CF L_{ω}(α < k) because the class CF L_{ω}(α < k) is closed under intersection with ω-regular languages. But this is not possible because B ∈ A(k) − CF L_{ω} holds by hypothesis. Thus

(D′_{A} ∪ B^{∼}) ∈ A(k) − CF L_{ω} = CF L_{ω}(α ≤ k) − CF L_{ω}(α < k)

[(3)] Assume that A ∈ A(k) − CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}, and B ∈ NA − CF L_{ω}. Then by Theorems 6.14 and 6.16, D′_{A} ∈ A(k) − CF L_{ω} and B^{∼} ∈ NA − CF L_{ω}. Hence

(D′_{A} ∪ B^{∼}) ∈ CF L_{ω}(α ≤ k)

because the class CF L_{ω}(α ≤ k) is closed under finite disjoint union.

And if (D′_{A}∪B^{∼}) was in the class CF L_{ω}(α < k) then for a fixed letter b ∈ X_{A}, the ω-language

A.(b. ↞)^{ω} = X_{A}^{⋆}.(b. ↞)^{ω} ∩ (D′_{A} ∪ B^{∼})

would be in CF L_{ω}(α < k) because the class CF L_{ω}(α < k) is closed under intersection with ω-regular languages. But then, as stated in the proof of Theorem 6.16, one could construct a PDA in P DA(α < k) accepting A. This is not possible because A ∈ A(k) − CF L holds by hypothesis. Thus

(D′_{A} ∪ B^{∼}) ∈ A(k) − CF L_{ω} = CF L_{ω}(α ≤ k) − CF L_{ω}(α < k)

[(4)] Assume that A ∈ A(k) − CF L, where k is an integer ≥ 2 or k = ℵ_{0}^{−}, and B ∈ A(k′) − CF L_{ω} where k is an integer ≥ 2 or k′ ∈ {ℵ_{0}^{−}, ℵ_{0}, 2^{ℵ_{0}}}. Then by Theorems 6.14 and 6.16, D′_{A} ∈ A(k) − CF L_{ω} and B^{∼} ∈ A(k′) − CF L_{ω}.

Hence D′_{A} and B^{∼} are in CF L_{ω}(α ≤ sup(k, k′)) and

(D′_{A} ∪ B^{∼}) ∈ CF L_{ω}(α ≤ sup(k, k′))

because this class is closed under finite disjoint union. With similar arguments as in the preceding cases, one can prove that (D′_{A}∪B^{∼}) is neither in CF L_{ω}(α < k) nor in CF L_{ω}(α < k′). Hence (D′_{A} ∪ B^{∼}) is not in CF L_{ω}(α < sup(k, k′)) and finally

(D′_{A} ∪ B^{∼}) ∈ A(sup(k, k′)) − CF L_{ω}
□

In order to obtain further results about ω-languages from results about conciliating sets, we shall use the above defined correspondence A → A^{d} between the conciliating hierarchy and the Wadge hierarchy. We shall then prove the following proposition.

Proposition 6.18 a) if A ⊆ Σ^{⋆} is a context free language in NA − CF L (respectively in A(k) − CF L), then A^{d} is an ω-CFL in NA − CF L_{ω} (respectively in A(k) − CF L_{ω}).

b) if A ⊆ Σ^{ω} is an ω-CFL in NA − CF L_{ω} (respectively in A(k) − CF L_{ω}), then A^{d} is an ω-CFL in NA − CF L_{ω} (respectively in A(k) − CF L_{ω}).

c) If A is the union of a finitary context free language B and of an ω-CFL C over the same alphabet Σ, then A^{d} = B^{d} ∪ C^{d} is an ω-CFL such that:

[B ∈ NA − CF L and C ∈ NA − CF L_{ω}] ⟶ A^{d} ∈ NA − CF L_{ω}

[B ∈ NA − CF L and C ∈ A(k) − CF L_{ω}] ⟶ A^{d} ∈ A(k) − CF L_{ω} [B ∈ A(k) − CF L and C ∈ NA − CF L_{ω}] ⟶ A^{d} ∈ A(k) − CF L_{ω} [B ∈ A(k)−CF L and C ∈ A(k′)−CF L_{ω}] ⟶ A^{d} ∈ A(sup(k, k′))−CF L_{ω}

Proof of a). Let A ⊆ Σ^{⋆} be a finitary context free language. We have proved in [Fin01a] that A^{d} is an ω-CFL. An easy construction, left to the reader, provides, from a PDA M such that L(M) = A, a BPDA M′ such that L(M′) = A^{d}. Moreover if M ∈ P DA(α ≤ k) then M′ ∈ BP DA(α ≤ k), hence if A is non ambiguous A^{d} is also a non ambiguous ω-CFL and if A is in A(k) − CF L then one can construct such a M′ in BP DA(α ≤ k). It remains to show that if A is in A(k) − CF L then A^{d} is not in CF L_{ω}(α < k). But

A.d^{ω} = A^{d} ∩ Σ^{⋆}.d^{ω}

Thus if A^{d} was in CF L_{ω}(α < k), the ω-language A.d^{ω} would be in CF L_{ω}(α < k) because this class is closed under intersection with ω-regular languages. And by proposition 5.17 the language A would then be in CF L(α < k) which would lead to a contradiction because we have assumed that A is in A(k) − CF L.

Proof of b). Let A ⊆ Σ^{ω} be an ω-CFL. We have proved in [Fin01a] that A^{d} is an ω-CFL. An easy construction, left to the reader, provides, from a BPDA M such that L(M) = A, a BPDA M′ such that L(M′) = A^{d} (intuitively the BPDA works as M but is blind to letters d). Again if M ∈ BP DA(α ≤ k) then M′ ∈ BP DA(α ≤ k), hence if A is non ambiguous so is A^{d}. And if A is inherently ambiguous of degree k, then one can construct, from a BPDA M ∈ BP DA(α ≤ k) accepting A, a BPDA M′ ∈ BP DA(α ≤ k) accepting A^{d}. It remains to show that if A is in A(k)−CF L_{ω} then A^{d} is not in CF L_{ω}(α < k). But

A = A^{d} ∩ Σ^{ω}

Thus if A^{d} was in CF L_{ω}(α < k), the ω-language A would be also in CF L_{ω}(α < k) and this is not possible because by hypothesis A was in A(k) − CF L_{ω}.

Proof of c). Let A be the union of a finitary context free language B and of an ω-CFL C over the same alphabet Σ. Then a) and b) imply that A^{d} = B^{d} ∪ C^{d} is an ω-CFL and that

[B ∈ NA − CF L and C ∈ NA − CF L_{ω}] ⟶ A^{d} ∈ NA − CF L_{ω}
[B ∈ NA − CF L and C ∈ A(k) − CF L_{ω}] ⟶ A^{d} ∈ CF L_{ω}(α ≤ k)
[B ∈ A(k) − CF L and C ∈ NA − CF L_{ω}] ⟶ A^{d} ∈ CF L_{ω}(α ≤ k)

[B ∈ A(k) − CF L and C ∈ A(k′) − CF L_{ω}] ⟶ A^{d} ∈ CF L_{ω}(α ≤ sup(k, k′))

because the classes NA − CF L_{ω} and CF L_{ω}(α ≤ k) are closed under finite disjoint union and B^{d} ∩ C^{d} = ∅.

It remains to show that in the second and third cases, A^{d} is not in CF L_{ω}(α < k) and in the last case that A^{d} is not in CF L_{ω}(α < sup(k, k′)). This may be seen with similar methods as above, because:

B.d^{ω} = A^{d} ∩ Σ^{⋆}.d^{ω}

C = A^{d} ∩ Σ^{ω}
□

6.4 Borel hierarchy and non ambiguous ω-CFL

From preceding theorems we first deduce that non ambiguous ω-CFL exhaust the finite ranks of the Borel hierarchy.

Theorem 6.19 For each integer n ≥ 1, there exist Σ_{n}^{0}-complete non ambiguous ω-CFL E_{n} and Π_{n}^{0}-complete non ambiguous ω-CFL F_{n}.

Proof. For n = 1 consider the Σ_{1}^{0}-complete ω-regular language E_{1} = {α ∈ {0, 1}^{ω}/∃i α(i) = 1} and the Π_{1}^{0}-complete ω-regular language F_{1} = {α ∈ {0, 1}^{ω}/∀i α(i) = 0}. These languages are non ambiguous omega context free languages because REG_{ω} ⊆ NA − CF L_{ω}. Now consider the Σ_{2}^{0}-complete ω-regular language E_{2} = {α ∈ {0, 1}^{ω}/∃^{<ω}i α(i) = 1} and the Π_{2}^{0}-complete ω-regular language F_{2} = {α ∈ {0, 1}^{ω}/∃^{ω}i α(i) = 0}, where ∃^{<ω}i means: ” there exist only finitely many i such that …” , and ∃^{ω}i means: ” there exist infinitely many i such that …”. E_{2} and F_{2} are non ambiguous omega context free languages because they are ω-regular languages.

To obtain non ambiguous omega context free languages further in the Borel hierarchy, consider now O_{1} (respectively C_{1} ) subsets of {0, 1}^{≤ω} such that (O_{1})^{d} (respectively (C_{1})^{d} ) are Σ_{1}^{0}-complete ( respectively Π_{1}^{0}-complete ) . For example O_{1} = {x ∈ {0, 1}^{≤ω} / ∃ i x(i) = 1} and C_{1} = {λ}.

We have to apply n ≥ 1 times the operation of exponentiation of sets. More precisely, we define, for a set A ⊆ X_{A}^{≤ω}: A^{∼.0} = A A^{∼.1} = A^{∼} and A^{∼.(n+1)} = (A^{∼.n})^{∼} .

Now apply n times (for an integer n ≥ 1) the operation ∼ (with different new letters ↞_{1}, ↞_{2}, ↞_{3},…, ↞_{n}) to O_{1} and C_{1}.

By Theorem 6.12, it holds that for an integer n ≥ 1: (O_{1}^{∼.n})^{d} is a Σ_{n+1}^{0}-complete subset of {0, 1, ↞_{1}, …, ↞_{n}, d}^{ω}. (C_{1}^{∼.n})^{d} is a Π_{n+1}^{0}-complete subset of {0, 1, ↞_{1}, …, ↞_{n}, d}^{ω}.

And it is easy to see that O_{1} and C_{1} are in the form A∪B where A is a finitary regular language and B is a regular ω-language, hence A is a non ambiguous context free finitary language and B is a non ambiguous context free ωlanguage. Then it follows from Theorem 6.16 and proposition 6.17 that the conciliating sets O_{1}^{∼.n} and C_{1}^{∼.n} are also in that form. Then the ω-languages (O_{1}^{∼.n})^{d} and (C_{1}^{∼.n})^{d} are in NA − CF L_{ω} by proposition 6.18.

Hence the class NA − CF L_{ω} exhausts the finite ranks of the hierarchy of Borel sets: we obtain the non ambiguous ω-CFL E_{n} = (O_{1}^{∼.(n−1)})^{d} and F_{n} = (C_{1}^{∼.(n−1)})^{d}, for n ≥ 3.

6.5 Borel hierarchy and ω-CFL which are inherently ambiguous of degree ≤ ℵ_{0}^{−}

We shall study ω-CFL which are inherently ambiguous of degree ≤ ℵ_{0}^{−}.

Recall that we have seen in Example 5.6 that if k is an integer ≥ 2 and

A_{k} = ⋃_{i=1}^{k}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}} … a_{2k−1}^{n_{k}}a_{2k}^{n_{k}} | n_{1}, …, n_{k} ≥ 1}

A_{∞} = A_{2}^{⋆}

Then A_{k} is inherently ambiguous of degree k over the alphabet Σ_{k} = {a_{1}, …, a_{2k}} and A_{∞} is inherently ambiguous of degree ℵ_{0}^{−} over the alphabet Σ_{2}.

Let then e be a new letter and

B_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{⋆}
C_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{ω}
D_{k} = B_{k} ∪ C_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{≤ω}
B_{∞} = A_{∞}.e.{a_{1}, …, a_{4}, e}^{⋆}
C_{∞} = A_{∞}.e.{a_{1}, …, a_{4}, e}^{ω}
D_{∞} = B_{∞} ∪ C_{∞} = A_{∞}.e.{a_{1}, …, a_{4}, e}^{≤ω}

We can infer from proposition 5.17 that C_{k} (respectively C_{∞}) is an ω-CFL which is inherently ambiguous of degree k (respectively ℵ_{0}^{−}), and one can easily prove in a similar manner that B_{k} (respectively B_{∞}) is a context free language which is inherently ambiguous of degree k (respectively ℵ_{0}^{−}), i.e.

B_{k} ∈ A(k) − CF L and C_{k} ∈ A(k) − CF L_{ω}

B_{∞} ∈ A(ℵ_{0}^{−}) − CF L and C_{∞} ∈ A(ℵ_{0}^{−}) − CF L_{ω}

Remark now that the ω-language (D_{k})^{d} = (B_{k} ∪ C_{k})^{d} (respectively (D_{∞})^{d} = (B_{∞}∪C_{∞})^{d}) is an open subset of {a_{1}, …, a_{2k}, e, d}^{ω} (respectively {a_{1}, …, a_{4}, e, d}^{ω}). But (D_{k})^{d} (respectively (D_{∞})^{d}) is not a closed set because otherwise the ωword (a_{1})^{ω} would be in (D_{k})^{d} (respectively (D_{∞})^{d}). This follows from the characterization of closed sets given in proposition 4.1, because for each integer n ≥ 1 the finite word (a_{1})^{n} is an initial prefix of some ω-word in (D_{k})^{d} (respectively (D_{∞})^{d}). Therefore (D_{k})^{d} (respectively (D_{∞})^{d}) is a Σ_{1}^{0}-complete subset of {a_{1}, …, a_{2k}, e, d} (respectively {a_{1}, …, a_{4}, e, d}).

Hence we can generate some ω-CFL which are inherently ambiguous of degree k (respectively ℵ_{0}^{−}) and further in the Borel hierarchy, using the operation of exponentiation of sets.

By Theorem 6.12, for every integer n ≥ 1, (D_{k}^{∼.n})^{d} (respectively (D_{∞}^{∼.n})^{d}) is a Σ_{n+1}^{0}-complete subset of (Σ_{k} ∪ {↞_{1}, …, ↞_{n}, e, d})^{ω} (respectively (Σ_{2} ∪ {↞_{1} , …, ↞_{n}, e, d})^{ω}).

D_{k} (respectively D_{∞}) is the union of a context free language in A(k) − CF L (respectively A(ℵ_{0}^{−}) − CF L) and of an ω-CFL in A(k) − CF L_{ω} (respectively A(ℵ_{0}^{−}) − CF L_{ω}). But then it follows from Theorem 6.16 and proposition 6.17 that the conciliating sets D_{k}^{∼.n} (respectively D_{∞}^{∼.n}) are also in that form. Then the ω-languages (D_{k}^{∼.n})^{d} (respectively (D_{∞}^{∼.n})^{d}) are in A(k) − CF L_{ω} (respectively A(ℵ_{0}^{−}) − CF L_{ω}) by proposition 6.18. So we have proved the following result:

Proposition 6.20 Let k be an integer ≥ 2 or k = ℵ_{0}^{−}. For each integer n ≥ 1, there exist Σ_{n}^{0}-complete ω-CFL in A(k) − CF L_{ω}, i.e. which are inherently ambiguous of degree k.

In order to construct ω-CFL which are inherently ambiguous of degree k ≤ ℵ_{0}^{−} and in the corresponding Π_{n}^{0} classes, we look first for some closed ω-CFL.

Return to the above example 5.6, for k an integer ≥ 2:

A_{k} = ⋃_{i=1}^{k}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}} … a_{2k−1}^{n_{k}}a_{2k}^{n_{k}} | n_{1}, …, n_{k} ≥ 1}

Then A_{k} is inherently ambiguous of degree k over the alphabet Σ_{k} = {a_{1}, …, a_{2k}}.

Let then e be a new letter and

B_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{⋆}
G_{k} = Adh(B_{k})

Consider first the case of G_{2} = Adh(B_{2}). It is easy to see that if σ is an ω-word in G_{2} then either the word σ contains at least an occurrence of the letter e and σ ∈ C_{2} = A_{2}.e.{a_{1}, a_{2}, a_{3}, a_{4}, e}^{ω} or σ is in the following form: a_{1}^{ω}, or a_{1}^{n}a_{2}^{ω}, for an integer n ≥ 1, or a_{1}^{n}a_{2}^{n}a_{3}^{ω}, for an integer n ≥ 1.

C_{2} is in A(2) − CF L_{ω} and each of the ω-languages: {a_{1}^{ω}}, {a_{1}^{n}a_{2}^{ω} | n ≥ 1}, {a_{1}^{n}a_{2}^{n}a_{3}^{ω} | n ≥ 1}, is a deterministic ω-CFL, hence is a non ambiguous ω-CFL. But the union of C_{2} and of these three ω-languages is disjoint thus G_{2} = Adh(B_{2}) is in CF L_{ω}(α ≤ 2) because this class is closed under finite disjoint union. But G_{2} is not in NA − CF L_{ω}: otherwise C_{2} = G_{2} ∩ Σ_{2}^{⋆}.e.(Σ_{2} ∪ {e})^{ω} would be non ambiguous because the class NA − CF L_{ω} is closed under intersection with ω-regular languages. Thus G_{2} = Adh(B_{2}) is in A(2)−CF L_{ω}.

G_{2} = Adh(B_{2}) is a closed subset of (Σ_{2} ∪ {e})^{ω} but (Adh(B_{2}))^{d} is not a closed subset of (Σ_{2} ∪ {e, d})^{ω}. If it was closed the word a_{1}^{n}.d^{ω}, for n ≥ 1, would be in (Adh(B_{2}))^{d} by proposition 4.1 because every initial segment a_{1}^{n}.d^{p} of a_{1}^{n}.d^{ω} may be extended to the ω-word a_{1}^{n}.d^{p}.a_{1}^{ω} ∈ (Adh(B_{2}))^{d} (a_{1}^{ω} ∈ Adh(B_{2})). But every word in (Adh(B_{2}))^{d} contains infinitely many letters in Σ_{2}∪{e} (Adh(B_{2}) contains only infinite words) thus a_{1}^{n}.d^{ω} is not in (Adh(B_{2}))^{d}.

We are now looking for a conciliating set in the form A ∪ B ⊆ X^{≤ω} where A ∈ A(2) − CF L and B ∈ A(2) − CF L_{ω} and (A ∪ B)^{d} is a closed subset of (X ∪ {d})^{ω}.

The set B_{2} ∪ Adh(B_{2}) is still not convenient for our purpose: (B_{2} ∪ Adh(B_{2}))^{d} is not closed. If it was closed (for example) the ω-words a_{1}^{n}.d^{ω}, for n ≥ 1, would be in (B_{2} ∪ Adh(B_{2}))^{d} because every initial segment a_{1}^{n}.d^{p} may be extended to the ω-word a_{1}^{n}.d^{p}.a_{1}^{ω} which is in (B_{2} ∪ Adh(B_{2}))^{d} (a_{1}^{ω} is in B_{2} ∪ Adh(B_{2})). But a_{1}^{n}.d^{ω} is not in (B_{2} ∪ Adh(B_{2}))^{d} because the finite word a_{1}^{n} is neither in B_{2} nor in Adh(B_{2}).

We see that we must add to B_{2}∪Adh(B_{2}) the set of finite words u over Σ_{2}∪{e} such that every prefix of u is a prefix of a word of B_{2}, i.e. the set of prefixes of words of B_{2}. By analogy with the adherence of a language we can set the following definition:

Definition 6.21 Let V ⊆ X^{⋆} be a finitary language over the alphabet X. The finite adherence of the language V is

Adh^{fin}(V) = {σ ∈ X^{⋆} | LF (σ) ⊆ LF (V)} = LF (V)

Proposition 6.22 Let V ⊆ X^{⋆} be a finitary language over the alphabet X. Then the ω-language (Adh^{fin}(V)∪Adh(V))^{d} is a closed subset of (X ∪{d})^{ω}.

Proof. Let V ⊆ X^{⋆} be a finitary language over the alphabet X. And let W = (Adh^{fin}(V) ∪ Adh(V))^{d}. We shall show, using proposition 4.1 that W is a closed subset of (X ∪ {d})^{ω}. Let then σ ∈ (X ∪ {d})^{ω}, such that [∀n ≥ 1, ∃u ∈ (X ∪{d})^{ω} such that σ(1) … σ(n).u ∈ W]. We see that for each integer n ≥ 1 the word σ[n](/d), obtained from σ[n] by removing every occurrence of the letter d, may be extended to a word in Adh^{fin}(V) or to an ω-word in Adh(V). Hence for each integer n ≥ 1 the word σ[n](/d) is a prefix of a word of V and then the (finite or infinite) word σ(/d) is in (Adh^{fin}(V) ∪ Adh(V)). Thus σ is in W = (Adh^{fin}(V) ∪ Adh(V))^{d} and this ends the proof that W is a closed subset of (X ∪ {d})^{ω}. □

Consider then the set Adh^{fin}(B_{2}). It is constituted of words of B_{2} and of words in one of the following sets of words: B_{2}^{1} = {a_{1}^{n} | n ≥ 0}, B_{2}^{2} = {a_{1}^{n}a_{2}^{p} | n ≥ 1 and p ≥ 1}, B_{2}^{3} = {a_{1}^{n}a_{2}^{n}a_{3}^{p} | n ≥ 1 and p ≥ 1}, B_{2}^{4} = {a_{1}^{n}a_{2}^{n}a_{3}^{p}a_{4}^{q} | n ≥ 1 and p ≥ 1 and 1 ≤ q ≤ p}, B_{2}^{5} = {a_{1}^{n}a_{2}^{p}a_{3}^{q} | n ≥ 1 and p ≥ 1 and 1 ≤ q ≤ p}, B_{2}^{6} = {a_{1}^{n}a_{2}^{p}a_{3}^{p}a_{4}^{q} | n ≥ 1 and p ≥ 1 and 1 ≤ q ≤ n},

It is easy to see that these languages B_{2}^{i}, for 1 ≤ i ≤ 6, are deterministic hence non ambiguous context free languages.

The union ⋃_{1≤i≤4} B_{2}^{i} is a disjoint union thus the language ⋃_{1≤i≤4} B_{2}^{i} is in NA − CF L. In a similar manner the union ⋃_{5≤i≤6} B_{2}^{i} is disjoint then the language ⋃_{5≤i≤6} B_{2}^{i} is in NA − CF L.

By a similar result for finitary languages as Theorem 5.16 c) for ω-CFL, we can deduce that ⋃_{1≤i≤6} B_{2}^{i} is in CF L(α ≤ 2) and then that

Adh^{fin}(B_{2}) = B_{2} ∪ ⋃_{1≤i≤6} B_{2}^{i} is in CF L(α ≤ 2)

because the union of B_{2} and ⋃_{1≤i≤6} B_{2}^{i} is a disjoint union. Moreover we can see that

Adh^{fin}(B_{2}) ∈ A(2) − CF L

because otherwise Adh^{fin}(B_{2}) would be non ambiguous and then

B_{2} = Adh^{fin}(B_{2}) ∩ Σ_{2}^{⋆}.e.(Σ_{2} ∪ {e})^{⋆}

would be also non ambiguous because the class NA − CF L is closed under intersection with rational languages.

Now the conciliating set W_{2} = Adh^{fin}(B_{2})∪Adh(B_{2}) is the union of a language in A(2) − CF L and of an ω-language in A(2) − CF L_{ω} and

(Adh^{fin}(B_{2}) ∪ Adh(B_{2}))^{d}

is a closed subset of (Σ_{2} ∪ {e, d})^{ω}. The ω-language (W_{2})^{d} is not an open subset of (Σ_{2}∪{e, d})^{ω} because otherwise there would exist a finitary language V ⊆ (Σ_{2} ∪ {e, d})^{⋆} such that (W_{2})^{d} = V.(Σ_{2} ∪ {e, d})^{ω}. But the ω-word d^{ω} is in (W_{2})^{d} (because the empty word is in Adh^{fin}(B_{2})) hence there would exist a finite word v ∈ V such that v = d^{n} for some integer n ≥ 0. Then the ω-word d^{n}.e^{ω} would be in (W_{2})^{d} but this is not possible because the ω-word e^{ω} is not in (Adh^{fin}(B_{2}) ∪ Adh(B_{2})).

(W_{2})^{d} is a closed and not open subset of (Σ_{2}∪{e, d})^{ω} hence it is a Π_{1}^{0}-complete subset of (Σ_{2} ∪ {e, d})^{ω}.

Now as above we can generate some ω-CFL which are inherently ambiguous of degree 2 and of greater topological complexity, using the operation of exponentiation of sets.

By Theorem 6.12, for every integer n ≥ 1, (W_{2}^{∼.n})^{d} is a Π_{n+1}^{0}-complete subset of (Σ_{2} ∪ {↞_{1}, …, ↞_{n}, e, d})^{ω}.

W_{2} is the union of a context free language in A(2) − CF L and of an ω-CFL in A(2) − CF L_{ω}. But then it follows from Theorem 6.16 and proposition 6.17 that the conciliating sets W_{2}^{∼.n} are also in that form. Then the ω-languages (W_{2}^{∼.n})^{d} are in A(2) − CF L_{ω} by proposition 6.18. So we have proved the following result:

Proposition 6.23 For each integer n ≥ 1, there exist Π_{n}^{0}-complete ω-CFL in A(2) − CF L_{ω}, i.e. which are inherently ambiguous of degree 2.

We are going now to extend this result to every finite degree of ambiguity. We then consider

B_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{⋆} and
W_{k} = Adh^{fin}(B_{k}) ∪ Adh(B_{k})

Firstly the ω-language Adh(B_{k}) is the union of the following ω-languages:

C_{k} = A_{k}.e.{a_{1}, …, a_{2k}, e}^{ω}

A = {a_{1}^{ω}}, and for 1 ≤ j < k:

A_{j}.a_{2j+1}^{ω} = ⋃_{i=1}^{j}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}}a_{2i+2}^{n_{i+1}} … a_{2j+1}^{ω} | n_{1}, …, n_{j} ≥ 1},

C_{k}^{j} = {a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2j−2}^{n_{j}}a_{2j−1}^{n_{j}}a_{2j}^{ω} | n_{1}, …, n_{j} ≥ 1}.

The ω-language A is regular hence it is a non ambiguous ω-CFL. And for every integer j, 1 ≤ j < k, the context free language A_{j} is inherently ambiguous of degree j hence the ω-CFL A_{j}.a_{2j+1}^{ω} is also inherently ambiguous of degree j by proposition 5.17. The union of these ω-languages is disjoint thus

A ∪ ⋃_{1≤j<k} A_{j}.a_{2j+1}^{ω} ∈ CF L_{ω}(α < k) = CF L_{ω}(α ≤ k − 1)

because the class CF L_{ω}(α < k) is closed under disjoint finite union.

On the other side it is easy to see that, for every integer j ∈ [1, k − 1], the ωlanguage C_{k}^{j} is a deterministic context free ω-CFL, hence C_{k}^{j} ∈ NA − CF L_{ω}. The languages C_{k}^{j} are disjoint thus their union is a non ambiguous ω-CFL by Theorem 5.16 (a).

And by Theorem 5.16 (c),

A ∪ ⋃_{1≤j<k} A_{j}.a_{2j+1}^{ω} ∪ ⋃_{1≤j<k} C_{k}^{j} ∈ CF L_{ω}(α ≤ (k − 1) + 1) = CF L_{ω}(α ≤ k)

We know also that C_{k} ∈ CF L_{ω}(α ≤ k) but C_{k} and the preceding union are disjoint, hence

Adh(B_{k}) = C_{k} ∪ A ∪ ⋃_{1≤j<k} A_{j}.a_{2j+1}^{ω} ∪ ⋃_{1≤j<k} C_{k}^{j} ∈ CF L_{ω}(α ≤ k)

because the class CF L_{ω}(α ≤ k) is closed under finite disjoint union. And Adh(B_{k}) is not in CF L_{ω}(α < k) because otherwise the ω-language

C_{k} = Adh(B_{k}) ∩ (Σ_{k})^{⋆}.e.(Σ_{k} ∪ {e})^{ω}

would be also in CF L_{ω}(α < k) because this class is closed under intersection with ω-regular languages. But this is not the case as C_{k} is inherently ambiguous of degree k.

Finally we have proved that Adh(B_{k}) ∈ A(k) − CF L_{ω}.

Consider now the set of finite words Adh^{fin}(B_{k}). This set is the union of the following sets of finite words:

B_{k},

B = {a_{1}^{n} | n ≥ 0}, and for 1 ≤ j < k:

A_{j}.(a_{2j+1})^{+} = ⋃_{i=1}^{j}{a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2i−1}^{n_{i}}a_{2i}^{n_{1}}a_{2i+1}^{n_{i+1}}a_{2i+2}^{n_{i+1}} … a_{2j+1}^{p} | n_{1}, …, n_{j}, p ≥ 1},

Ā_{j} = A_{j}.{a_{2j+1}^{p}.a_{2j+2}^{q} | p ≥ 1 and 1 ≤ q ≤ p},

B_{k}^{j} = {a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2j−2}^{n_{j}}a_{2j−1}^{n_{j}}a_{2j}^{p} | n_{1}, …, n_{j}, p ≥ 1},

B̄_{k}^{j} = {a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2j−2}^{n_{j}}a_{2j−1}^{n_{j}}a_{2j}^{p}a_{2j+1}^{q} | n_{1}, …, n_{j}, p ≥ 1 and 1 ≤ q ≤ p},

B̄_{k} = {a_{1}^{n_{1}}a_{2}^{n_{2}}a_{3}^{n_{2}} … a_{2k−2}^{n_{k}}a_{2k−1}^{n_{k}}a_{2k}^{p} | n_{1}, …, n_{k}, ≥ 1 and 1 ≤ p ≤ n_{1}}.

The language B is regular thus it is a deterministic, hence non ambiguous, context free language. For each integer j ∈ [1, k − 1], the language A_{j} is an inherently ambiguous context free language of degree j, thus A_{j}.(a_{2j+1})^{⋆} is also an inherently ambiguous context free language of degree j < k, (by a similar result as proposition 5.17 for finitary languages). It is also easy to see that the language Ā_{j} is in CF L(α ≤ j), because one can find a PDA in P DA(α ≤ j) accepting Ā_{j} from a PDA in P DA(α ≤ j) accepting A_{j}.

The union B ∪ ⋃_{1≤j<k} A_{j}.(a_{2j+1})^{+} ∪ ⋃_{1≤j<k} Ā_{j} is disjoint thus

B ∪ ⋃_{1≤j<k} A_{j}.(a_{2j+1})^{+} ∪ ⋃_{1≤j<k} Ā_{j} is in CF L(α < k) = CF L(α ≤ k − 1)

because the class CF L(α < k) is closed under finite disjoint union.

Considering the other languages above, it is easy to see that the languages B_{k}^{j}, B̄_{k}^{j}, for 1 ≤ j < k, and B̄_{k} are deterministic hence non ambiguous context free languages.

These languages are disjoint, then

B̄_{k} ∪ ⋃_{1≤j<k} B_{k}^{j} ∪ ⋃_{1≤j<k} B̄_{k}^{j} is in NA − CF L

because the class NA − CF L is closed under disjoint finite union.

By a similar result for finitary languages as Theorem 5.16 c) for ω-CFL, we can deduce that

B ∪ ⋃_{1≤j<k} A_{j}.(a_{2j+1})^{+} ∪ ⋃_{1≤j<k} Ā_{j} ∪ ⋃_{1≤j<k} B_{k}^{j} ∪ ⋃_{1≤j<k} B̄_{k}^{j} ∪ B̄_{k}

is in CF L(α ≤ (k − 1) + 1) = CF L(α ≤ k).

And Adh^{fin}(B_{k}) is the union of B_{k} and of this above language in CF L(α ≤ k). Then Adh^{fin}(B_{k}) is in CF L(α ≤ k) because it is the disjoint union of two languages in CF L(α ≤ k).

But Adh^{fin}(B_{k}) is not in CF L(α < k) because otherwise

B_{k} = Adh^{fin}(B_{k}) ∩ Σ_{k}^{⋆}.e.(Σ_{k} ∪ {e})^{⋆}

would be also in CF L(α < k) because this class is closed under intersection with regular languages. And B_{k} ∈ A(k)−CF L hence it is not in CF L(α < k).

Finally we have proved that

Adh^{fin}(B_{k}) ∈ A(k) − CF L

And the conciliating set W_{k} = Adh^{fin}(B_{k})∪Adh(B_{k}) is the union of a language in A(k) − CF L and of an ω-language in A(k) − CF L_{ω} and

(Adh^{fin}(B_{k}) ∪ Adh(B_{k}))^{d}

is a closed subset of (Σ_{k} ∪ {e, d})^{ω}. The ω-language (W_{k})^{d} is not an open subset of (Σ_{k} ∪{e, d})^{ω} because otherwise there would exist a finitary language V ⊆ (Σ_{k} ∪ {e, d})^{⋆} such that (W_{k})^{d} = V.(Σ_{k} ∪ {e, d})^{ω}. But the ω-word d^{ω} is in (W_{k})^{d} (because the empty word is in Adh^{fin}(B_{k})) hence there would exist a finite word v ∈ V such that v = d^{n} for some integer n ≥ 0. Then the ω-word d^{n}.e^{ω} would be in (W_{k})^{d} but this is not possible because the ω-word e^{ω} is not in (Adh^{fin}(B_{k}) ∪ Adh(B_{k})).

(W_{k})^{d} is a closed and not open subset of (Σ_{k}∪{e, d})^{ω} hence it is a Π_{1}^{0}-complete subset of (Σ_{k} ∪ {e, d})^{ω}.

Now we can again generate some ω-CFL which are inherently ambiguous of degree k and of greater topological complexity, using the operation of exponentiation of sets.

By Theorem 6.12, for every integer n ≥ 1, (W_{k}^{∼.n})^{d} is a Π_{n+1}^{0}-complete subset of (Σ_{k} ∪ {↞_{1}, …, ↞_{n}, e, d})^{ω}.

W_{k} is the union of a context free language in A(k) − CF L and of an ω-CFL in A(k) − CF L_{ω}. But then it follows from Theorem 6.16 and proposition 6.17 that the conciliating sets W_{k}^{∼.n} are also in that form. Then the ω-languages (W_{k}^{∼.n})^{d} are in A(k) − CF L_{ω} by proposition 6.18. So we have proved the following result:

Proposition 6.24 Let k be an integer ≥ 2. For each integer n ≥ 1, there exist Π_{n}^{0}-complete ω-CFL F_{n}(k) in A(k) − CF L_{ω}, i.e. which are inherently ambiguous of degree k.

In order to extend this result to ω-CFL which are inherently ambiguous of degree ℵ_{0}^{−}, we shall use a result of Crestin:

Theorem 6.25 (Crestin [Cre72]) Let Σ = {a, b} and

C = {u.v / u, v ∈ {a, b}^{+} and u^{R} = u and v^{R} = v}

Then the language C is a context free language which is inherently ambiguous of infinite degree (i.e. C ∈ A(ℵ_{0}^{−}) − CF L).

In fact C = L_{p}^{2} where L_{p} = {v ∈ {a, b}^{+} / v^{R} = v} is the language of palindromes over the alphabet {a, b}.

Consider now the language

D = C.e.{a, b, e}^{⋆}

where e is a new letter. Then it is easy to see that

Adh(D) = {a, b}^{ω} ∪ C.e.{a, b, e}^{ω}
Adh^{fin}(D) = {a, b}^{⋆} ∪ C.e.{a, b, e}^{⋆}

because every word u ∈ {a, b}^{⋆} is a prefix of a palindrome (for example of the palindrome u.u^{R}) hence it is also a prefix of a word of C and of a word of D.

The ω-language C being in A(ℵ_{0}^{−}) − CF L, the ω-language C.e.{a, b, e}^{ω} is an ω-CFL which is in A(ℵ_{0}^{−}) − CF L_{ω} by proposition 5.17. On the other side the ω-language {a, b}^{ω} is regular hence it is a non ambiguous ω-CFL. Thus Adh(D) ∈ CF L_{ω}(α ≤ ℵ_{0}^{−}) because the class CF L_{ω}(α ≤ ℵ_{0}^{−}) is closed under finite disjoint union. And Adh(D) is not in CF L_{ω}(α < ℵ_{0}^{−}) because otherwise the ω-language

C.e.{a, b, e}^{ω} = Adh(D) ∩ {a, b}^{⋆}.e.{a, b, e}^{ω}

would be also in CF L_{ω}(α < ℵ_{0}^{−}) because the class CF L_{ω}(α < ℵ_{0}^{−}) is closed under intersection with ω-regular languages. But this is not possible because C.e.{a, b, e}^{ω} ∈ A(ℵ_{0}^{−}) − CF L_{ω}. Finally we have proved that

Adh(D) ∈ A(ℵ_{0}^{−}) − CF L_{ω}

Consider now the finitary language Adh^{fin}(D) = {a, b}^{⋆} ∪ C.e.{a, b, e}^{⋆}. In a similar manner (details are here left to the reader) we can show that

Adh^{fin}(D) ∈ A(ℵ_{0}^{−}) − CF L

Consider now the conciliating set

W = Adh(D) ∪ Adh^{fin}(D)

which is the union of a language in A(ℵ_{0}^{−}) − CF L and of an ω-language in A(ℵ_{0}^{−}) − CF L_{ω}. Then

(W)^{d} = (Adh^{fin}(D) ∪ Adh(D))^{d}

is a closed subset of {a, b, e, d}^{ω}. The ω-language (W)^{d} is not an open subset of {a, b, e, d}^{ω} because otherwise there would exist a finitary language V ⊆ {a, b, e, d}^{⋆} such that (W)^{d} = V.{a, b, e, d}^{ω}. But the ω-word d^{ω} is in (W)^{d} (because the empty word is in Adh^{fin}(D)) hence there would exist a finite word v ∈ V such that v = d^{n} for some integer n ≥ 0. Then the ω-word d^{n}.e^{ω} would be in (W)^{d} but this is not possible because the ω-word e^{ω} is not in (Adh^{fin}(D) ∪ Adh(D)).

(W)^{d} is a closed and non open subset of {a, b, e, d}^{ω} hence it is a Π_{1}^{0}-complete subset of {a, b, e, d}^{ω}.

Now reasoning as above, by Theorem 6.12, for every integer n ≥ 1, (W^{∼.n})^{d} is a Π_{n+1}^{0}-complete subset of {↞_{1}, …, ↞_{n}, a, b, e, d}^{ω}.

W is the union of a context free language in A(ℵ_{0}^{−}) − CF L and of an ω-CFL in A(ℵ_{0}^{−}) − CF L_{ω}, thus it follows from Theorem 6.16 and proposition 6.17 that the conciliating sets W^{∼.n} are also in that form. Then the ω-languages (W^{∼.n})^{d} are in A(ℵ_{0}^{−}) − CF L_{ω} by proposition 6.18. So we have proved the following result:

Proposition 6.26 For each integer n ≥ 1, there exist Π_{n}^{0}-complete ω-CFL which are inherently ambiguous of degree ℵ_{0}^{−}.

We can now summarize the preceding propositions in the following Theorem:

Theorem 6.27 Let k be an integer ≥ 2 or k = ℵ_{0}^{−}. Then for each integer n ≥ 1, there exist Σ_{n}^{0}-complete ω-CFL E_{n}(k) and Π_{n}^{0}-complete ω-CFL F_{n}(k) which are in A(k) − CF L_{ω}, i.e. which are inherently ambiguous of degree k.

7 Concluding remarks and further work

We will pursue the study of the above section by considering in [Fin00d] Borel sets which are ω-CFL in A(ℵ_{0}) − CF L_{ω} or in A(2^{ℵ_{0}}) − CF L_{ω}.

The Wadge Hierarchy is a great refinement of the Borel hierarchy and it is natural to ask for the restriction of the Wadge Hierarchy to several classes of ω-languages. In fact there is an effective version of the Wadge Hierarchy restricted to ω-regular languages. This hierarchy is now called the Wagner hierarchy and has length ω^{ω}. Wagner [Wag79] gave an automata structure characterization, based on notion of chain and superchain, for an automaton to be in a given class. And one can also compute the Wadge degree of any ω-regular language. Wilke and Yoo proved in [WY95] that one can compute the Wadge degree of any ω-regular language in polynomial time.

The Wadge hierarchy of deterministic ω-CFL has been determined. It has length ω^{ω^{2}}. It has been recently studied in [DFR01] [Dup99] [Fin99] [Fin01c].

We proved in [Fin01b] that the length of the Wadge hierarchy of ω-CFL (including non deterministic ω-CFL) is an ordinal greater than or equal to the Cantor ordinal ε_{0}.

Using the results and methods of this paper and of [Fin01b], we will show in [Fin00b] that the Wadge hierarchy restricted to the class NA − CF L_{ω} (respectively A(k) − CF L_{ω}, for k ≥ 2) has still a length ≥ ε_{0}.

In the last section we have constructed closed ω-CFL in A(k) − CF L_{ω} by taking the adherence of a finitary language in A(k) − CF L. One may ask for the preservation of unambiguity (respectively of inherent ambiguity) by the operation: V → Adh(V) and also by the operations: V → V^{ω} and: V → V^{δ}, which are fundamental operations from finitary languages to ω-languages. We prove in another paper that each of these operations preserves neither unambiguity nor inherent ambiguity, [Fin00c].

A further line of research is the study of context free grammars generating context free ω-languages. It seems that one could extend the equivalence between the existence of a non ambiguous grammar generating a CFL L and the existence of a non ambiguous PDA accepting L to the case of ω-languages. We then could study the links between the ambiguity of a finitary language L(G) generated by a context free grammar G and the ambiguity of the context free ω-language L_{ω}(G) generated by the same grammar G.

In a recent work, Wich distinguishes ambiguous grammars of infinite degree by the growth-rate of their ambiguity with respect to the length of the words. He shows in [Wic99] that each cycle-free context-free grammar G is either exponentially ambiguous or its ambiguity is bounded by a polynomial. It should be possible, as suggested by Simonnet, to show, at least for special classes of grammars, that a grammar which is exponentially ambiguous generates an ω-CFL in A(2^{ℵ_{0}}) − CF L_{ω} and that a grammar (of infinite degree of ambiguity) whose ambiguity is bounded by a polynomial generates an ω-CFL in A(ℵ_{0}) − CF L_{ω}.

Acknowledgements. Thanks to Jean-Pierre Ressayre and Jacques Duparc for many useful discussions about Wadge and Wagner Hierarchies, and to Pierre Simonnet for communicating his result on analytic omega context free languages.

References

[Arn83b] A. Arnold, Rational Omega-Languages are Non-Ambiguous, Theoretical Computer Science 26 (1983), 221-223

[Arn83a] A. Arnold, Topological Characterizations of Infinite Behaviours of Transition Systems, ICALP 1983: 28-38.

[ABB96] J-M. Autebert, J. Berstel and L. Boasson, Context Free Languages and Pushdown Automata, in Handbook of Formal Languages, Vol 1, Springer Verlag 1996.

[Bea84a] D. Beauquier, Langages Algébriques Infinitaires, Ph. D. Thesis, Université Paris 7, 1984.

[Bea84b] D. Beauquier, Some Results about Finite and Infinite Behaviours of a Pushdown Automaton, Proceedings of the 11^{th} International Colloquium on Automata, languages and Programming (ICALP 84) LNCS 172, p. 187-195 (1984).

[Ber79] J. Berstel, Transductions and Context Free Languages, Teubner Studienbücher Informatik, 1979.

[BN80] L. Boasson and M. Nivat, Adherences of Languages, J. Comput. System Sci. 20 (1980) 3, 285-309.

[Büc60a] J.R. Büchi, Weak Second Order Arithmetic and Finite Automata, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 6 (1960), pp 66-92.

[Büc60b] J.R. Büchi, On a Decision Method in Restricted Second Order Arithmetic, Logic Methodology and Philosophy of Science, ( Proc. 1960 Int. Congr. ). Stanford University Press, 1962, 1-11.

[BL69] J.R. Büchi and L. H. Landweber, Solving Sequential Conditions by Finite State Strategies. Trans. Amer. Math. Soc. 138 (1969).

[BS73] J.R. Büchi, D. Siefkes, The Monadic Second Order Theory of All Countable Ordinals, Decidable Theories 2, 1973, S.L.N.M. , number 328.

[CP97] O. Carton and D. Perrin, Chains and Superchains for ω-Rational Sets, Automata and semigroups, International Journal of Algebra and Computation Vol. 7, no. 7(1997), p. 673-695.

[CP99] O. Carton and D. Perrin, The Wagner Hierarchy of ω-Rational Sets, International Journal of Algebra and Computation, Vol. 9, no. 5 (1999), p. 597-620.

[Cre72] J.P. Crestin, Un Langage non Ambigu dont le Carré est d’ Ambiguité Inhérente non Bornée, Proc. 1st ICALP Colloquium, pp. 377-390, North Holland (1972).

[CG77] R. S. Cohen and A. Y. Gold, Theory of ω-Languages, Parts one and two, J. Computer and System Science 15 (1977) 2, 169-184 and 185-208.

[CG78] R. S. Cohen and A. Y. Gold, ω-Computations on Deterministic Pushdown Machines, J. Computer and System Science (1978) 3, 257-300.

[Dup95a] J. Duparc, La Forme Normale des Boréliens de Rang Fini, Ph.D. Thesis, Université Paris 7, 1995.

[Dup95b] J. Duparc, The Normal Form of Borel Sets, Part 1: Borel Sets of Finite Rank, C.R.A.S. Paris, t.320, Série 1, p.651-656, 1995.

[Dup01] J. Duparc, Wadge Hierarchy and Veblen Hierarchy: Part 1: Borel Sets of Finite Rank, Journal of Symbolic Logic, 66 (2001), no. 1, p. 56-86.

[Dup99] J. Duparc, A Hierarchy of Context Free Omega Languages, Theoretical Computer Science, to appear.

[DFR01] J. Duparc, O. Finkel and J-P. Ressayre, Computer Science and the Fine Structure of Borel Sets, Theoretical Computer Science, Vol 257 (1-2), April 2001, p.85-105.

[Eil74] S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.

[EH93] J. Engelfriet and H. J. Hoogeboom, X-Automata on ω-Words, Theoretical Computer Science 110 (1993) 1, 1-51.

[Fin99] O. Finkel, Wadge Hierarchy and Deterministic Omega Context Free Languages, in preparation.

[Fin00a] O. Finkel, Borel Hierarchy and Omega Context Free Languages, Theoretical Computer Science, to appear.

[Fin00b] O. Finkel, Wadge Hierarchy and Ambiguity in Omega Context Free Languages, in preparation.

[Fin00c] O. Finkel, Non Preservation of Ambiguity from Finitary to Omega Context Free Languages, preprint, 10 pages.

[Fin00d] O. Finkel, On Omega Context Free Languages which are Inherently Ambiguous of Infinite Degree, in preparation.

[Fin01a] O. Finkel, Topological Properties of Omega Context Free Languages, Theoretical Computer Science, Vol 262 (1-2), July 2001, p. 669-697.

[Fin01b] O. Finkel, Wadge Hierarchy of Omega Context Free Languages, Theoretical Computer Science, Volume 269 (1-2), 2001, p.283-315.

[Fin01c] O. Finkel, An Effective Extension of the Wagner Hierarchy to Blind Counter Automata, Proceedings of Computer Science Logic 2001, Lecture Notes in Computer Science, Volume 2142, p. 369-383.

[Fin01d] O. Finkel, On Omega Context Free Languages which are Borel Sets of Infinite Rank, Theoretical Computer Science, to appear.

[Fla85] P. Flajolet, Ambiguity and Transcendence, Research Report Number 397, INRIA, May 1985.

[Fla86] P. Flajolet, Analytic Models and Ambiguity of Context Free Languages, Research Report Number 483, INRIA, January 1986.

[Gin66] S. Ginsburg, The Mathematical Theory of Context Free Languages, Mc Graw-Hill Book Company, New York, 1966.

[GU66] S. Ginsburg and J.S. Ulllian, Ambiguity in Context Free Languages, JACM 13 (1), 62-89 (1966).

[Her97] C. Herzog, Pushdown Automata with Bounded Nondeterminism and Bounded Ambiguity, Theoretical Computer Science 181, 1997.

[HU69] J.E. Hopcroft and J.D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley Publishing Company, Reading, Massachussetts, 1969.

[Kur66] K. Kuratowski, Topology, Academic Press, New York 1966.

[Lan69] L. H. Landweber, Decision Problems for ω-Automata, Math. Syst. Theory 3 (1969) 4,376-384.

[LT94] H. Lescow and W. Thomas, Logical Specifications of Infinite Computations, In:”A Decade of Concurrency” (J. W. de Bakker et al., eds), Springer LNCS 803 (1994), 583-621.

[Lin76] M. Linna, On ω-Sets Associated with Context-Free Languages, Inform. Control 31 (1976) 3, 272-293.

[Lin77] M. Linna, A Decidability Result for Deterministic ω-Context-Free Languages, Theoretical Computer Science 4 (1977), 83-98.

[MaN66] R. Mac Naughton, Testing and Generating Infinite Sequences by a Finite Automaton, Information and Control 9 (1966), 521-530.

[Mau68] H. A. Maurer, The Existence of Context Free Languages which are Inherently Ambiguous of any Degree, Dept. of Mathematics, Research Series, University of Calgary, 1968.

[Mau69] H. A. Maurer, A Direct Proof of the Inherent Ambiguity of a Simple Context Free Language, Journal of the Association for Computing Machinery, Vol 16, Number 2, April 1969, 256-260.

[Mos80] Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam 1980.

[Naj98] M. Naji, Grad der Mehrdeutigkeit Kontextfreier Grammatiken und Sprachen, Diplomarbeit, FB Informatik, Johann-Wolfgang-Goethe-Universität, Frankfurt am Main, 1998.

[Niv77] M. Nivat, Mots Infinis Engendrés par une Grammaire Algébrique, RAIRO Infor. théor. 11 (1977), 311-327.

[Niv78] M. Nivat, Sur les Ensembles de Mots Infinis Engendrés par une Grammaire Algébrique, RAIRO Infor. théor. 12 (1978), 259-278.

[PP01] D. Perrin and J.-E. Pin, Infinite Words, Book in preparation, available from http://www.liafa.jussieu.fr/jep/Resumes/InfiniteWords.html

[Sch67] J.R. Schoenfield, Mathematical Logic, Addison-Wesley, Reading, MA, 1967.

[Sel98] V. Selivanov, Fine Hierarchy of Regular ω-Languages, Theoretical Computer Science 191(1998) p.37-59.

[Sim92] P. Simonnet, Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992.

[Sim00] P. Simonnet, personal communication, April 2000.

[Sta86] L. Staiger, Hierarchies of Recursive ω-Languages, Jour. Inform. Process. Cybernetics EIK 22 (1986) 5/6, 219-241.

[Sta97a] L. Staiger, ω-Languages, Chapter of the Handbook of Formal Languages, Vol 3, edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin, 1997.

[Sta97b] L. Staiger, On ω-Power Languages, in New Trends in Formal Languages, Control, Coperation, and Combinatorics, Lecture Notes in Computer Science 1218, Springer-Verlag, Berlin 1997, 377-393.

[SW74] L. Staiger and K. Wagner, Automatentheoretische und Automatenfreie Charakterisierungen Topologischer Klassen Regulärer Folgenmengen. Elektron. Informationsverarb. Kybernetik EIK 10 (1974) 7, 379-392.

[Tho90] W. Thomas, Automata on Infinite Objects, in: J. Van Leeuwen, ed., Handbook of Theorical Computer Science, Vol. B ( Elsevier, Amsterdam, 1990 ), p. 133-191.

[Wad84] W.W. Wadge, Reducibility and Determinateness on the Baire Space, Ph. D. Thesis, Berkeley, 1984.

[Wag79] K. Wagner, On Omega Regular Sets, Inform. and Control 43 (1979) p. 123-177.

[Wic99] K. Wich, Exponential Ambiguity of Context-free Grammars, Proc. of 4th Int. Conf. on Developments in Language Theory 1999, World Scientific, Singapore.

[Wic00] K. Wich, Sublinear Ambiguity, Proc. of MFCS 2000, Lecture Notes in Computer Science Vol. 1893, Springer, 2000, p. 690-698.

[WY95] Th. Wilke and H. Yoo, Computing the Wadge Degree, the Lifschitz Degree and the Rabin Index of a Regular Language of Infinite Words in Polynomial Time, in: TAPSOFT’ 95: Theory and Practice of Software Development (eds. P.D. Mosses, M. Nielsen and M.I. Schwartzbach), L.N.C.S. 915, p. 288-302, 1995.