Alternation (formal language theory)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In formal language theory and pattern matching, alternation is the union of two sets of strings or patterns. As a pattern, the alternation of a and b matches either a or b.

In formal language theory, alternation is commutative and associative. This is not in general true in pattern-matching languages.

In the SNOBOL language, regular expression syntax, and some other languages, alternation is a binary infix operator on patterns, notated "|".


  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X.