formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...

and

pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...

, alternation is the union of two sets of strings, or equivalently the

logical disjunction In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is ...

of two patterns describing sets of strings.

Regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

s are closed under alternation, meaning that the alternation of two regular languages is again regular. In implementations of

regular expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...

s, alternation is often expressed with a vertical bar connecting the expressions for the two languages whose union is to be matched, while in more theoretical studies the

plus sign The plus sign () and the minus sign () are mathematical symbols used to denote positive and negative functions, respectively. In addition, the symbol represents the operation of addition, which results in a sum, while the symbol represents ...

may instead be used for this purpose. The ability to construct

finite automata A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...

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. Other classes of languages that are closed under alternation include

context-free language In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, mos ...

s and

recursive language In mathematics, logic and computer science, a recursive (or ''decidable'') language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the forma ...

s. The vertical bar notation for alternation is used in the

SNOBOL SNOBOL ("StriNg Oriented and symBOlic Language") is a series of programming languages developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph Griswold and Ivan P. Polonsky, culminating in SNOBOL4. It was one of a ...

language and some other languages. In formal language theory, alternation is

commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Perhaps most familiar as a pr ...

and

associative In mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for express ...

. 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

Bibliography

* John E. Hopcroft and Jeffrey D. Ullman, ''Introduction to Automata Theory, Languages and Computation'', Addison-Wesley Publishing, Reading Massachusetts, 1979. . Combinatorics on words Operators (programming) String (computer science) {{combin-stub