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.

Regular languages are closed under alternation, meaning that the alternation of two regular languages is again regular.^[1] In regular expressions, alternation is often expressed with a vertical bar connecting the expressions for the two languages whose union is to be matched.^[2] The same notation is used in the SNOBOL language and some other languages.

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

References

^ Linz, Peter (2006). "Theorem 4.1". An Introduction to Formal Languages and Automata. Jones & Bartlett Learning. pp. 100–101. ISBN 9780763737986.
^ Fitzgerald, Michael (2012). "Alternation". Introducing Regular Expressions: Unraveling Regular Expressions, Step-by-Step. O'Reilly Media. pp. 43–45. ISBN 9781449338893.

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.

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

[1] Linz, Peter (2006). "Theorem 4.1". An Introduction to Formal Languages and Automata. Jones & Bartlett Learning. pp. 100–101. ISBN 9780763737986.

[2] Fitzgerald, Michael (2012). "Alternation". Introducing Regular Expressions: Unraveling Regular Expressions, Step-by-Step. O'Reilly Media. pp. 43–45. ISBN 9781449338893.

[1]

[2]