patternMinor
Can the plus operator in regex be replaced by the star operator?
Viewed 0 times
canthestaroperatorreplacedplusregex
Problem
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!
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!
Solution
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).
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).
Context
StackExchange Computer Science Q#13470, answer score: 9
Revisions (0)
No revisions yet.