The adherences of languages as topological spaces. (English) Zbl 0571.68057

Head, Tom

Automata on infinite words, Ec. Printemps Inf. Théor., Le Mont Dore 1984, Lect. Notes Comput. Sci. 192, 147-163 (1985).

[For the entire collection see Zbl 0563.00019.]
The problem of characterizing the topological spaces that arise as adherences of languages of specified types is raised and pertinent concepts of general topology are reviewed. It is observed that the spaces that arise as adherences of arbitrary languages may be characterized as either: (1) the closed subsets of the Cantor ternary set; (2) the zero- dimensional compact metrizable spaces; or (3) the Stone spaces of the countable Boolean algebras. R. S. Pierce’s concept of a space of finite type is reviewed and his theorem characterizing the zero-dimensional compact metric spaces of finite type by means of an associated finite structural invariant is reviewed. It is shown that a topological space is homeomorphic with the adherence of a regular language if and only if it is zero-dimensional compact metrizable and of finite type. The structural invariant of the adherence of a regular language is algorithmically constructible from any automaton recognizing the language. Comparing these invariants provides a procedure for deciding homeomorphism of adherences for regular languages.

MSC:

68Q45	Formal languages and automata
54H99	Connections of general topology with other structures, applications
54A05	Topological spaces and generalizations (closure spaces, etc.)

Keywords:

Cantor ternary set; zero-dimensional compact metrizable spaces; Stone spaces; countable Boolean algebras; space of finite type; regular language; structural invariant; homeomorphism

Citations:

Zbl 0563.00019