Tagged Questions
2
votes
1answer
112 views
Two elementary question on automaton and language
1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language?
PS:The reason ...
2
votes
2answers
106 views
How to ensure the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$
Show that the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$ in the sense that, for every semigroup $S$ recognizing $X$, there exists a morphism from $S$ onto the syntactic ...
12
votes
1answer
327 views
Eilenberg's rational hierarchy of nonrational automata & languages
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational ...
