patternMinor
Where/when did Stephen Kleene first define the Kleene closure/star?
Viewed 0 times
thestardidwherestephenfirstdefinewhenkleeneclosure
Problem
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?
Is there a paper by Kleene in which he first defines the Kleene closure?
Solution
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. $EF$ 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.
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. $EF$ 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.
Context
StackExchange Computer Science Q#24237, answer score: 8
Revisions (0)
No revisions yet.