4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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 "+".

$\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.