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 L1 and L2 are languages over some common alphabet.
- The concatenation L1L2 consists of all strings of the form vw where v is a string from L1 and w is a string from L2.
- The intersection L1 ∩ L2 of L1 and L2 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 = x1…xn over some alphabet, let wR = xn…x1,
- 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
Read more about this topic: Formal Language
Famous quotes containing the words operations and/or languages:
“There is a patent office at the seat of government of the universe, whose managers are as much interested in the dispersion of seeds as anybody at Washington can be, and their operations are infinitely more extensive and regular.”
—Henry David Thoreau (1817–1862)
“People in places many of us never heard of, whose names we can’t pronounce or even spell, are speaking up for themselves. They speak in languages we once classified as “exotic” but whose mastery is now essential for our diplomats and businessmen. But what they say is very much the same the world over. They want a decent standard of living. They want human dignity and a voice in their own futures. They want their children to grow up strong and healthy and free.”
—Hubert H. Humphrey (1911–1978)