Editing Formal language (section)

== Operations on languages ==

Certain operations on languages are common. This includes the standard set operations, such as union, intersection, and complement. Another class of operation is the element-wise application of string operations.

Examples: suppose <math>L_1</math> and <math>L_2</math> are languages over some common alphabet <math>\Sigma</math>.
* The ''[[concatenation]]'' <math>L_1 \cdot L_2</math> consists of all strings of the form <math>vw</math> where <math>v</math> is a string from <math>L_1</math> and <math>w</math> is a string from <math>L_2</math>.
* The ''intersection'' <math>L_1 \cap L_2</math> of <math>L_1</math> and <math>L_2</math> consists of all strings that are contained in both languages
* The ''complement'' <math>\neg L_1</math> of <math>L_1</math> with respect to <math>\Sigma</math> consists of all strings over <math>\Sigma</math> that are not in <math>L_1</math>.
* The [[Kleene star]]: the language consisting of all words that are concatenations of zero or more words in the original language;
* ''Reversal'':
** Let ''ε'' be the empty word, then <math>\varepsilon^R = \varepsilon</math>, and
** for each non-empty word <math>w = \sigma_1 \cdots \sigma_n</math> (where <math>\sigma_1, \ldots, \sigma_n</math>are elements of some alphabet), let <math>w^R = \sigma_n \cdots \sigma_1</math>,
** then for a formal language <math>L</math>, <math>L^R = \{ w^R \mid w \in L \}</math>.
* [[String homomorphism]]

Such [[string operations]] are used to investigate [[Closure (mathematics)|closure properties]] of classes of languages. A class of languages is closed under a particular operation when the operation, applied to languages in the class, always produces a language in the same class again. For instance, the [[context-free language]]s are known to be closed under union, concatenation, and intersection with [[regular language]]s, but not closed under intersection or complement. The theory of [[cone (formal languages)|trios]] and [[abstract family of languages|abstract families of languages]] studies the most common closure properties of language families in their own right.<ref>{{harvtxt|Hopcroft|Ullman|1979}}, Chapter 11: Closure properties of families of languages.</ref>

:{| class="wikitable"
|+ align="top"|Closure properties of language families (<math>L_1</math> Op <math>L_2</math> where both <math>L_1</math> and <math>L_2</math> are in the language family given by the column). After Hopcroft and Ullman.
|-
! Operation
!
! [[Regular language|Regular]]
! [[DCFL]]
! [[Context free language|CFL]]
! [[Indexed language|IND]]
! [[Context sensitive language|CSL]]
! [[Recursive language|recursive]]
! [[Recursively enumerable language|RE]]
|-
|[[Union (set theory)|Union]]
|<math>L_1 \cup L_2 = \{w \mid w \in L_1 \lor w \in L_2\} </math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|[[Intersection (set theory)|Intersection]]
|<math>L_1 \cap L_2 = \{w \mid w \in L_1 \land w \in L_2\}</math>
| {{Yes}}
| {{No}}
| {{No}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|[[Complement (set theory)|Complement]]
|<math>\neg L_1 = \{w \mid w \not\in L_1\}</math>
| {{Yes}}
| {{Yes}}
| {{No}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{No}}
|-
|[[Concatenation]]
|<math>L_1\cdot L_2 = \{wz \mid w \in L_1 \land z \in L_2\}</math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Kleene star
|<math>L_1^{*} = \{\varepsilon\} \cup \{wz \mid w \in L_1 \land z \in L_1^{*}\}</math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|(String) homomorphism <math>h</math>
|<math>h(L_1) = \{h(w) \mid w \in L_1\}</math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{No}}
| {{No}}
| {{Yes}}
|-
|ε-free (string) homomorphism <math>h</math>
|<math>h(L_1) = \{h(w) \mid w \in L_1\}</math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Substitution <math>\varphi</math>
|<math>\varphi(L_1) = \bigcup_{\sigma_1 \cdots \sigma_n \in L_1} \varphi(\sigma_1) \cdot \ldots \cdot \varphi(\sigma_n)</math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{No}}
| {{Yes}}
|-
|Inverse homomorphism <math>h^{-1}</math>
|<math>h^{-1}(L_1) = \bigcup_{w \in L_1} h^{-1}(w)</math>
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Reverse
|<math>L^R = \{w^R \mid w \in L\} </math>
| {{Yes}}
| {{No}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Intersection with a [[regular language]] <math>R</math>
|<math>L \cap R = \{w \mid w \in L \land w \in R\}</math>
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
<!--
|-
|Min
|
| {{Yes}}
| {{Yes}}
| {{No}}
| {{?}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Max
|
| {{Yes}}
| {{Yes}}
| {{No}}
| {{?}}
| {{No}}
| {{No}}
| {{No}}
|-
|Init
|
| {{Yes}}
| {{No}}
| {{Yes}}
| {{?}}
| {{No}}
| {{No}}
| {{Yes}}
|-
|Cycle
|
| {{Yes}}
| {{No}}
| {{Yes}}
| {{?}}
| {{Yes}}
| {{Yes}}
| {{Yes}}
|-
|Shuffle
|
| {{Yes}}
| {{?}}
| {{Yes}}
| {{?}}
| {{?}}
| {{?}}
| {{Yes}}
|-
|Perfect Shuffle
|
| {{Yes}}
| {{?}}
| {{?}}
| {{?}}
| {{?}}
| {{?}}
| {{Yes}}
-->
|}