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
    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
    The "monoid-recognizable" are all languages if you don't restrict to finite monoids, since every language is recognized by $A^*$.2014-07-16