display | more...

In the field of computation theory, there are three regular operations: union, concatenation and star. These are operations which can be applied to languages to generate new languages. They form the basis of regular expressions, an alternative to finite automata and regular grammars for specifying regular languages.

The unifying property of regular operations is the fact regular languages are closed under them. That is, if one of the regular operations is applied to one (star) or two (union and concatenation) regular languages, the resulting language is regular. In fact, this closure holds for context-free languages and turing-recognizable languages as well. This property (often used together with the pumping lemma, can be useful in proving the regularity of a language.

A very simple example is proving that the language {0m1n | m, n0} is regular. Note that this is also simple to prove using regular expressions or finite automata, but for the sake of example, we'll use the closure of regular operations.

Let A = {0}, B = {1} and C = {0m1n | m, n0}. Since A and B are finite languages, we can say with certainty that they are regular. If the star operation is applied to A the result is {0m | m0}. Since regular languages are closed under the star operation, A* is also regular. The same argument can be made for B*. Now, if we apply the concatenation operation to A* and B*, the result is C (any number of 0s followed by any number of 1s). Since we have already shown that A* and B* are regular, and regular languages are closed under concatenation, we have now proved that C is regular. That was easy.

The regular operations are important because they are the building blocks for describing languages, but their closure properties are not terribly useful for proving things. However, the closure properties of the complement and intersection can be very useful.

Log in or register to write something here or to contact authors.