Formal Language - Operations On Languages

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 L₁ and L₂ are languages over some common alphabet.

• The concatenation L₁L₂ consists of all strings of the form vw where v is a string from L₁ and w is a string from L₂.
• The intersection L₁ ∩ L₂ of L₁ and L₂ consists of all strings which are contained in both languages
• The complement ¬L of a language with respect to a given alphabet consists of all strings over the alphabet that are not in the language.
• The Kleene star: the language consisting of all words that are concatenations of 0 or more words in the original language;
• Reversal:
  • Let e be the empty word, then eR = e, and
  • for each non-empty word w = x₁…x_n over some alphabet, let wR = x_n…x₁,
  • then for a formal language L, LR = {wR | w ∈ L}.
• String homomorphism

Such string operations are used to investigate 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 languages are known to be closed under union, concatenation, and intersection with regular languages, but not closed under intersection or complement. The theory of trios and abstract families of languages studies the most common closure properties of language families in their own right.

Closure properties of language families ( Op where both and are in the language family given by the column). After Hopcroft and Ullman.

Operation		Regular	DCFL	CFL	IND	CSL	recursive	RE
Union		Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection		Yes	No	No	No	Yes	Yes	Yes
Complement		Yes	Yes	No	No	Yes	Yes	No
Concatenation		Yes	No	Yes	Yes	Yes	Yes	Yes
Kleene star		Yes	No	Yes	Yes	Yes	Yes	Yes
Homomorphism		Yes	No	Yes	Yes	No	No	Yes
e-free Homomorphism		Yes	No	Yes	Yes	Yes	Yes	Yes
Substitution		Yes	No	Yes	Yes	Yes	No	Yes
Inverse Homomorphism		Yes	Yes	Yes	Yes	Yes	Yes	Yes
Reverse		Yes	No	Yes	Yes	Yes	Yes	Yes
Intersection with a regular language		Yes	Yes	Yes	Yes	Yes	Yes	Yes