Alternation (formal language theory)

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Magic links bot (talk | contribs) at 17:28, 25 May 2017 (Replace magic links with templates per local RfC and MediaWiki RfC). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.


Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Alternation_(formal_language_theory)&oldid=782229427"