[Solved]: Kleene plus in Thompson's construction

Problem Detail: 

Is there a direct way to represent Kleene plus(+) using Thompson's construction algorithm?

When I studied Thompson's construction I learned how to transform concatenation, union and kleene star of regular expresions directly into a NFA.

In wikipedia(and other websites) I found the same thing I learned in college(nothing about Kleene plus):Thompson's construction

In a non-direct method we can always transform $R^+$ in $RR^*$ and then use Thompson construction.

There is a website that transform regular expressions into NFA. They claim to use Thompson-McNaughton-Yamada algorithm. Here they transform $a^+$ into:

Is this some kind of extension of Thompson's construction algorithm?

Asked By : Renato Sanhueza

Answered By : Pseudonym

It's technically an "extension" in the sense that Ken Thompson's original paper (ACM DL subscription required) doesn't mention it. This is presumably because his regular expression compiler didn't support "+" syntax in 1968.

However, pretty much every textbook presentation of Thompson's algorithm (e.g. see Bruce Watson's 1995 review paper on FA construction) mentions it. It's likely that no one person "extended" the method in Thompson's paper, or the "extension" was done by Thompson when he decided to support "+".

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents