Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Wandering Logic Apr 29 at 21:50
    
(From the wikipedia page about Regular Expressions, I have never seen the paper, so don't know if it's exactly the right one.) –  Wandering Logic Apr 29 at 21:51
3  
"If E and F are events already constructed, then by E*F 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? –  Hendrik Jan Apr 29 at 22:18

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.