2
$\begingroup$

By the Myhill–Nerode theorem a language $L$ is accepted by a finite automaton iff it consists of classes of a finite congruence. By the Kleene theorem $L$ is accepted by a finite automaton iff it is regular.

Does somebody know a direct proof (without automata) of the proposition: "$L$ consists of classes of a finite congruence iff it is regular"?

Thank you in advance.

Improve this question
$\endgroup$
6
  • $\begingroup$ For the purpose of this question, do you define a regular language as one given by a regular expression? $\endgroup$
    – Joel David Hamkins
    Nov 24, 2013 at 17:58
  • $\begingroup$ @Joel David Hamkins: Yes, certainly. $\endgroup$
    – Boris Novikov
    Nov 24, 2013 at 19:46
  • $\begingroup$ Which direction are you unhappy with? A nondeterministic automaton is almost trivially a semigroup of relations and so going from automata to semigroups is easy. Would you like an argument going directly from semigroups to regular expressions? Actually most things work nicely at the semigroup level except Kleene star. $\endgroup$
    – Benjamin Steinberg
    Nov 25, 2013 at 1:08
  • $\begingroup$ @Benjamin Steinberg: Thank you very much. I consider a regular language rather as a set, which is constructed by join, multiplication, and Kleene star. I proved for "preautomata" (partial action of a free semigroup) an analogue of the Myhill–Nerode theorem, but can not get the Kleene theorem. It seems that it is impossible to build a nondeterministic preautomaton, so I search a direct proof. $\endgroup$
    – Boris Novikov
    Nov 25, 2013 at 14:08
  • 1
    $\begingroup$ But is your problem going from sets recognized by monoids to regular expressions or going from regular expressions to sets recognized by monoids? To show the * of a set recognized by a monoid is also recognized by a monoid is the trickiest part if you don't allow nondeterminism. $\endgroup$
    – Benjamin Steinberg
    Nov 25, 2013 at 15:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.