
Accession Number : AD0692421
Title : NONDETERMINISTIC AUTOMATA AND EFFECTIVE LANGUAGES.
Descriptive Note : Technical rept.,
Corporate Author : IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Personal Author(s) : Walljasper,Stanley J.
Report Date : AUG 1969
Pagination or Media Count : 131
Abstract : In the dissertation, the concept of a finite automation is extended to a nondeterministic automaton over any arbitrary semigroup. The languages recognized by these nondeterministic 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 nondeterministic automata to computable sets or formal languages, a specific type of computable semigroup called sigmaeffective semigroup is introduced. Then associated classes of effective languages are defined. It is shown that for any sigmaeffective semigroup one can constructively find another which is finitely generated such that the two effective languages are the same.
Descriptors : (*COMPUTATIONAL LINGUISTICS, AUTOMATA), GROUPS(MATHEMATICS), PROGRAMMING LANGUAGES, GRAMMARS, SET THEORY, MATHEMATICAL MODELS
Subject Categories : Linguistics
Computer Programming and Software
Bionics
Distribution Statement : APPROVED FOR PUBLIC RELEASE