Alternation (formal language theory)

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 "|".

References

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.

This article is issued from Wikipedia - version of the 10/4/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.