Tagged Questions
0
votes
0answers
82 views
Whether $L=\{(a^m,a^n)\}^*$ is regular or not ?
I am condidering the automatic structure for Baumslag-Solitar semigroups. And I have a question. For any $m,n \in Z$, whether the set $L=\{(a^m,a^n)\}^*$ is regular or not. Here a set is regular means ...
2
votes
1answer
117 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
328 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 ...
