Foundations: Alphabets, Strings & Languages

Sigma-plus

/ Sigma is the Greek capital Σ; plus is the + sign /

Sigma-plus, written Σ+, is almost the same giant bag as Σ*, but with the empty string left out. It is the set of every non-empty string over the alphabet: every string that has at least one symbol in it. If Σ = {a, b}, then Σ+ contains a, b, aa, ab, ba, bb, aaa, and so on, but not ε.

Formally, Σ+ is the set of all strings over Σ of length one or more. The relationship to Σ* is simple and worth memorizing: Σ* = Σ+ with ε added in, and equivalently Σ+ = Σ* with ε removed. You can also describe Σ+ as the union of the length-1 strings, length-2 strings, length-3 strings, and so on, omitting only the length-0 layer (which is just ε). Like Σ*, it is countably infinite whenever the alphabet has at least one symbol.

Why bother having a separate name for almost the same set? Because the empty string is genuinely special and sometimes you must exclude it. Many definitions hinge on whether ε is allowed: for instance the plus operator on a language, L+, is the Kleene star L* without (necessarily) the empty string. Being precise about whether you mean Σ* or Σ+ keeps the empty-string corner cases from silently sneaking into or out of your languages.

For Σ = {a}, Σ+ = {a, aa, aaa, ...} (no ε), while Σ* = {ε, a, aa, aaa, ...}. The only difference is the single string ε.

Σ+ is Σ* minus the empty string: exactly the non-empty strings.

The only difference between Σ* and Σ+ is whether ε is included. Σ* has it; Σ+ does not. That one string is exactly the point of the distinction.

Also called
Σ+non-empty stringspositive closure所有非空字串