HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can the plus operator in regex be replaced by the star operator?

Submitted by: @import:stackexchange-cs··
0
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!

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).

Context

StackExchange Computer Science Q#13470, answer score: 9

Revisions (0)

No revisions yet.