2
$\begingroup$

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.

  • 0
    "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.2012-04-13
  • 0
    @ 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.2012-04-13
  • 0
    I think that [this](http://www.liafa.jussieu.fr/~jep/PDF/York1.pdf) 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".2012-04-13
  • 0
    In that case "rational" and "regular" turn out to be equivalent.2012-04-13
  • 1
    @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.2012-04-13
  • 0
    @ dtldarek:Thanks.So if it is in FSM,all of them are equivalent?Since I saw the rational is equivalent to recognizable in the paper you gave above,Mark also told that rational and regular are equivalent right now.2012-04-13
  • 0
    Sorry, I do not understand what you are asking.2012-04-13
  • 0
    When semigroups or monoids are involved, the term "regular" is not used for this -- "recognizable" is the preferred term -- because [regular semigroup](http://en.wikipedia.org/wiki/Regular_semigroup) or monoid is used for something else, dating to an important 1951 paper in basic semigroup theory.2012-04-13

1 Answers 1

2

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.

  • 0
    @ 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.2012-05-15
  • 0
    @Andylang: No problem. I actually used your question as a motivation to finally get around to reading about these things in Berstel's book.2012-05-15
  • 0
    The "monoid-recognizable" are all languages if you don't restrict to finite monoids, since every language is recognized by $A^*$.2014-07-16