Alternation (formal language theory)
In formal language theory and pattern matching, alternation is the union of two sets of strings, or equivalently the logical disjunction of two patterns describing sets of strings.
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.[4]
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
associative
. 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
- ^ ISBN 9780763737986.
- ISBN 9781449338893.
- ^ "Alternation with The Vertical Bar". regular-expressions.info. Retrieved 2021-11-11.
- ISBN 9780080916613.
Bibliography
- 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.
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |