Topology and ambiguity in \(\omega\)-context free languages (Q1781923)

In this paper the connection between the topological complexity of an \(\omega\)-context-free language (\(\omega\)-CF laguage) and its degree of ambiguity is shown. The \(\omega\)-CF languages are accepted by Büchi Pushdown Automata (BPDA), and the degree of ambiguity of a given infinite word is the number of different accepting runs in the automaton for this word. Using descriptive set theory it is proved that if \(L(A)\) is a non-Borel \(\omega\)-CF language accepted by BPDA \(A\), then there exist \(2^{\aleph_0}\) infinite words such that they have \(2^{\aleph_0}\) accepting runs in \(A\), where \(2^{\aleph_0}\) is the cardinality of the continuum. It follows that neither non-ambiguity nor inherent ambiguity are preserved by taking the adherence or the \(\delta\)-limit of a finitary CF language. The adherence of the set \(W\) of finite words is the set of all infinite words such that the set prefixes of an infinite word is a subset of the set of prefixes of \(W\), and the \(\delta\)-limit of \(W\) is a set of infinite words having infinitely many prefixes in \(W\). Also topology and ambiguity of infinitary rational relations is studied.