[Solved]: Where/when did Stephen Kleene first define the Kleene closure/star?

Problem Detail: 

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?

Asked By : Cornstalks

Answered By : Wandering Logic

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24237