Full disclosure, I'm interested in what this means about transformations on NFAs, but regex expressions seem like a easy way to ask the question.

If you have a regex that uses the plus operator (match one or more) can it, in the general case, be transformed into a regex that uses only the star operator (match zero or more).

Since all regular expressions can be converted into an NFA, and all NFAs can be converted into a regular expression (assuming the alphabet is the unicode character set lol), if it's true for one, it's true for both.

An hand-contrived example regex:


A regex recognizing the same language, without the + operator:


This may seem intuitively true for such a simple example, but I'd like to know for certain that it is generally true. Also, is there an algorithm that can convert an NFA containing a plus-like flow into a star-like flow NFA? Thanks!

  • $\begingroup$ "assuming the alphabet is the unicode character set" - this assumption is superfluous (I realize it may have been added in jest). The languages that can be described by regular expressions are exactly the languages that can be recognized by NFAs. The alphabet is irrelevant. Regarding r+ = rr*, that's just syntactic sugar. $\endgroup$ – G. Bach Jul 28 '13 at 15:36
  • $\begingroup$ This is how $\_^+$ is usually defined. Prove equivalence of your regexes by induction with arbitrary expressions "underneath" the $+$. $\endgroup$ – Raphael Jul 29 '13 at 8:05

True. For any regular expression $R$, (the meaning of) $R^+$ equals $R \cdot R^*$, and conversely, $R^*$ equals $R^+\mid\varepsilon$ (where $\mid$ here is the choice operator 'or', and $\varepsilon$ the expression matching the empty string).

Thus in any regular expression dialect it suffices to include only one of star and plus without loosing expressibility. Translation of plus into star can be done recursively (inside-out).


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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