In formal language theory and pattern matching, alternation is the

union Union commonly refers to: * Trade union, an organization of workers * Union (set theory), in mathematics, a fundamental operation on sets Union may also refer to: Arts and entertainment Music * Union (band), an American rock group ** ''Un ...

of two sets of strings, or equivalently the

logical disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...

of two patterns describing sets of strings. Regular languages are

closed Closed may refer to: Mathematics * Closure (mathematics), a set, along with operations, for which applying those operations on members always results in a member of the set * Closed set, a set which contains all its limit points * Closed interval, ...

under alternation, meaning that the alternation of two regular languages is again regular. In implementations of regular expressions, alternation is often expressed with a vertical bar connecting the expressions for the two languages whose union is to be matched, while in more theoretical studies the

plus sign The plus and minus signs, and , are mathematical symbols used to represent the notions of positive and negative, respectively. In addition, represents the operation of addition, which results in a sum, while represents subtraction, result ...

may instead be used for this purpose. The ability to construct finite automata for unions of two regular languages that are themselves defined by finite automata is central to the equivalence between regular languages defined by automata and by regular expressions. Other classes of languages that are closed under alternation include context-free languages and recursive languages. The vertical bar notation for alternation is used in the SNOBOL language and some other languages. In formal language theory, alternation is commutative and

associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...

. This is not in general true of the form of alternation used in pattern-matching languages, because of the side-effects of performing a match in those languages.

References

Bibliography

* John E. Hopcroft and Jeffrey D. Ullman, ''Introduction to Automata Theory, Languages and Computation'', Addison-Wesley Publishing, Reading Massachusetts, 1979. . Combinatorics on words Operators (programming) String (computer science) {{combin-stub