NON-DETERMINISTIC AUTOMATA AND EFFECTIVE LANGUAGES.
Abstract
In the dissertation, the concept of a finite automation is extended to a non-deterministic automaton over any arbitrary semigroup. The languages recognized by these non-deterministic automata are also characterized by regular expressions. Then a specific subclass of these automata is defined as deterministic automata which are characterized by congruences of finite index on the semigroup. The closure properties of these languages are then examined. In order to relate the languages recognized by non-deterministic automata to computable sets or formal languages, a specific type of computable semigroup called sigma-effective semigroup is introduced. Then associated classes of effective languages are defined. It is shown that for any sigma-effective semigroup one can constructively find another which is finitely generated such that the two effective languages are the same.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1969
- Accession Number
- AD0692421
Entities
People
- Stanley J. Walljasper
Organizations
- University of Iowa