4.4.2.3–4.4.2.4 - Regular expressions and regular languages (Java)

Languages as sets of strings

A formal language is a set of strings built from a specified alphabet, and a regular expression is a compact way to describe certain such sets.

For alphabet $\Sigma=\{a,b\}$, each string is a finite sequence of these symbols. The empty string, written $\varepsilon$, contains no symbols. A language need not contain every possible string over its alphabet. For example, the language of non-empty strings beginning with a contains a, aa, ab, aaa, aab and many more, but excludes $\varepsilon$, b and ba.

The expression a(a|b)* describes that example. It requires an initial a, followed by zero or more choices of a or b. Zero repetitions of the final group leave the initial a, so the shortest accepted string has length one. This expression describes an infinite set using finite notation; it does not instruct a program to generate all its members.

Repetition, choice and grouping

Regular-expression operators specify which parts may repeat, which alternatives are allowed and which parts belong together.

Juxtaposition means concatenation: ab requires an a then a b. A repetition operator attaches to the preceding item or group. Thus ab* accepts a, ab, abb, whereas (ab)* accepts empty, ab, abab. Grouping changes the set described. A task using another metacharacter must supply its meaning; these five operators are the required simple set.

To build an expression, translate each rule in order. “One or more a or b symbols, followed by an optional c” becomes (a|b)+c?. It accepts a, bb, abc, but not empty, c or acb: the optional c is at the end. To check a candidate, allocate its symbols to the required parts of the pattern and check that none are left over. Merely containing a permitted substring is not the same as belonging to the whole language.

Equivalence with finite-state machines

A regular expression and a finite-state machine can define exactly the same set of accepted strings.