Course contentsShow
← Computer Science
Lesson 1771 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Plus Operator and One-or-More Repetitions

Learn the + operator as shorthand for one-or-more repetitions and its relationship to Kleene star.

Plus Operator and One-or-More Repetitions

You'll learn the + operator as a convenient shorthand for matching one or more repetitions of a pattern.


The Core Idea

In the previous lesson, you learned about the Kleene star (*), which matches zero or more occurrences of a pattern. The plus operator (+) is very similar, but with one key difference: it requires at least one occurrence.

Think of it like this: if Kleene star says "have as many as you want, including none," the plus operator says "have as many as you want, but you must have at least one."

Formal Definition

For any regular expression R, the expression R+ denotes the language:

L(R+) = L(R · R*) = L(R) concatenated with L(R*)

In other words:

  • R+ = one copy of R, followed by zero or more additional copies
  • R+ matches R, RR, RRR, RRRR, ...
  • But R+ does not match the empty string (unlike R*)

Examples

  • a+ matches: "a", "aa", "aaa", ... (but not the empty string "")
  • (01)+ matches: "01", "0101", "010101", ... (sequences of "01" repeated one or more times)
  • (a|b)+ matches any non-empty string of a's and b's

Why It Matters

The plus operator is simply syntactic sugar—you could always write R · R* instead—but it makes regular expressions more readable when you need "at least one." Many practical patterns require at least one occurrence (e.g., "a valid identifier must have at least one character").

Key Takeaway: The + operator matches one or more repetitions of a pattern, equivalent to R · R*, and is shorthand for patterns that require at least one occurrence.