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 why I ask these two questions are mainly as follows:
(i)I can find out the definition of $recognizable$ instead of $recognize$ in Wikipedia.And I have got a definition of $recognize$ but feel a little confused about that.So I want to have a relatively authoritative definition.
(ii)In several books,the words $recognizable,rational$ and $regular$ are mentioned when they discuss about automaton and language.And I think they are actually equivalent in my own sense.But I am not sure about that and not able to prove it.So I want to ask whether my point is right or not here to help myself to understand the books deeply.

  • $\begingroup$ "Recognizable" usually means that there is an algorithm which decides whether a given string is in the language. "Regular" usually means that the language is recognizable, and that one can give a bound $M$ on the amount of memory used by the algorithm, without knowing the input string ahead of time. With these definitions, there are recognizable languages which are not regular; the canonical example is the set of strings {01, 0011, 000111, 00001111, …}. I don't know what "rational" means. $\endgroup$ – MJD Apr 13 '12 at 14:45
  • $\begingroup$ @ Mark Dominus:On Lothaire's book,a subset $X$ of $A^*$is rational if it can be obtained from the finite subsets of A by a finite number of the operations of union,product,and star. $\endgroup$ – Andylang Apr 13 '12 at 15:01
  • $\begingroup$ I think that this paper explains it pretty well. Besides, it is really easy to find all this definitions using Google, e.g. searching "recognizable language", "regular language" or "rational language". $\endgroup$ – dtldarek Apr 13 '12 at 15:23
  • $\begingroup$ In that case "rational" and "regular" turn out to be equivalent. $\endgroup$ – MJD Apr 13 '12 at 15:36
  • 1
    $\begingroup$ @MarkDominus I cannot agree with you. In different contexts "recognizable" means different things. If the context is a Turing machine, you are right, however, if the context is finite automata, the answer is different (and I do talk about mathematical notion, not just natural language). It is easy to find a bunch of articles using the term in Turing-recognizable sense, and others using it in FSM-recognizable meaning. Finally, I admit that from the articles I have read, the Turing-recognizable sense is indeed more frequent. $\endgroup$ – dtldarek Apr 13 '12 at 15:43

Please don't consider this as an authoritative answer, because I don't know much about this myself.

I got the following definition from Section 2.1 of these notes, and I think it's probably what you are looking for.

Definition We say that a language $L\subseteq A^*$ is recognised by a monoid $M$ if there is a morphism $h: A^*\rightarrow M$ and $X\subseteq M$ such that $L = h^{-1}(X)$.

I expect that the definition for semigroups just involves replacing 'monoid' by 'semigroup' and $A^*$ by $A^+$, but I don't have a reference for that.

In the notes I linked to, there's a theorem (right after the definition I quoted) saying that a language is regular if and only if it is recognized by a finite monoid. So the regular languages are the same as the class of languages recognized by finite monoids, which are a strict subclass of the 'monoid-recognizable' languages.

I think that unfortunately different people mean different things by the term 'recognizable language'. As Mark mentioned in the comments, 'recognizable' is often taken to mean 'recognizable by a Turing machine', i.e. recursively enumerable. But in the context of your question, 'recognizable language' is more likely to mean 'recognizable subset of $A^*$', and these turn out to be exactly the regular languages. Similarly 'rational language' means 'rational subset of $A^*$', and by Kleene's Theorem these are the same as the recognizable languages. So indeed in this context all three terms refer to the same class of languages.
The first two sections of Chapter III of Berstel's book are a good reference for this.

This paper by Jean-Eric Pin looks like a good introduction, but I haven't read it yet.

  • $\begingroup$ @ Tara B:Yes,I have read Jean-Eric Pin's paper and got a relatively deep point of the question.And thank's for your detailed explanation.I think that I agree with your statement above. $\endgroup$ – Andylang May 15 '12 at 15:19
  • $\begingroup$ @Andylang: No problem. I actually used your question as a motivation to finally get around to reading about these things in Berstel's book. $\endgroup$ – Tara B May 15 '12 at 15:30
  • $\begingroup$ The "monoid-recognizable" are all languages if you don't restrict to finite monoids, since every language is recognized by $A^*$. $\endgroup$ – Denis Jul 16 '14 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.