5
$\begingroup$

I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure.

Is there a paper by Kleene in which he first defines the Kleene closure?

$\endgroup$
  • 2
    $\begingroup$ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. Automata Studies. Princeton University Press. pp. 3–42. $\endgroup$ – Wandering Logic Apr 29 '14 at 21:50
  • $\begingroup$ (From the wikipedia page about Regular Expressions, I have never seen the paper, so don't know if it's exactly the right one.) $\endgroup$ – Wandering Logic Apr 29 '14 at 21:51
  • 3
    $\begingroup$ "If E and F are events already constructed, then by EF we shall mean the event which consists of zero or more consecutive occurrences of E preceded by one of F." ... "The reason we do not define E separately as ..." rand.org/pubs/research_memoranda/RM704.html (Rand 1951 Research Memorandum). @Wandering Logic can you make this an answer? $\endgroup$ – Hendrik Jan Apr 29 '14 at 22:18
7
$\begingroup$

Kleene's classic paper on finite automata and regular expressions is

Kleene, Stephen C.: "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. Automata Studies, Princeton University Press. pp. 3–42., 1956.

There seems to be a scan or recreation of that version of the paper at: http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf.

But, as pointed out by @HendrickJan, the work seems to have been done about 5 years earlier. The article starts with a note that says that "the material ... is drawn from Project RAND Research Memorandum RM-704 (15 Dec 1951, 101 pages) ... used by permission of the RAND Corporation ... supported by the RAND Corporation during the summer of 1951." A scan of the RAND research memorandum is available for free from the RAND website: http://www.rand.org/pubs/research_memoranda/RM704.html.

"Regular events" are defined in Section 7 of both papers. (page 46 of the 1951 memorandum and page 23 of the 1956 paper). Interestingly, Kleene defines $*$, the closure operator, as a binary operator, rather than a unary operator as we do today. This enables Kleene to avoid dealing with empty strings. $E*F$ means the same thing it does today: "0 or more instances of E followed by F" but there is no way to say $E^*$ and have it include the empty string.

$\endgroup$

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.