Alternation (formal language theory) (original) (raw)
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. Regular languages are closed under alternation, meaning that the alternation of two regular languages is again regular. In implementations of regular expressions, 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 may instead be used for this purpose. The ability to construct 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.
| Property | Value |
|---|---|
| dbo:abstract | 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. Regular languages are closed under alternation, meaning that the alternation of two regular languages is again regular. In implementations of regular expressions, 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 may instead be used for this purpose. The ability to construct 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. 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 commutative and 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. (en) |
| dbo:wikiPageID | 37612285 (xsd:integer) |
| dbo:wikiPageLength | 2769 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1054740944 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Combinatorics_on_words dbr:Regular_expression dbr:Commutative dbr:SNOBOL dbr:Context-free_language dbc:Operators_(programming) dbc:String_(computer_science) dbr:Formal_language dbr:Logical_disjunction dbr:Regular_language dbr:Recursive_language dbr:Plus_sign dbr:Associative dbr:Pattern_matching dbr:Union_(set_theory) dbr:Finite_automaton |
| dbp:wikiPageUsesTemplate | dbt:Combin-stub dbt:ISBN |
| dct:subject | dbc:Combinatorics_on_words dbc:Operators_(programming) dbc:String_(computer_science) |
| gold:hypernym | dbr:Union |
| rdf:type | dbo:Organisation |
| rdfs:comment | 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. Regular languages are closed under alternation, meaning that the alternation of two regular languages is again regular. In implementations of regular expressions, 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 may instead be used for this purpose. The ability to construct 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. (en) |
| rdfs:label | Alternation (formal language theory) (en) |
| owl:sameAs | freebase:Alternation (formal language theory) wikidata:Alternation (formal language theory) https://global.dbpedia.org/id/4Pv2a |
| prov:wasDerivedFrom | wikipedia-en:Alternation_(formal_language_theory)?oldid=1054740944&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Alternation_(formal_language_theory) |
| is dbo:wikiPageDisambiguates of | dbr:Alternation |
| is dbo:wikiPageRedirects of | dbr:Alternation_(formal_languages) dbr:Alternation_(pattern_matching) dbr:Pattern_alternation |
| is dbo:wikiPageWikiLink of | dbr:Regular_expression dbr:Vertical_bar dbr:Concatenation dbr:SNOBOL dbr:Alternation_(formal_languages) dbr:Backus–Naur_form dbr:Alternation dbr:Extended_Backus–Naur_form dbr:Pattern_matching dbr:Alternation_(pattern_matching) dbr:Pattern_alternation |
| is foaf:primaryTopic of | wikipedia-en:Alternation_(formal_language_theory) |