Closure Properties of Regular Languages to Know for Formal Language Theory

Closure properties of regular languages show how these languages behave under various operations like union, concatenation, and more. Understanding these properties is key in Formal Language Theory, as they help define and manipulate regular languages effectively.

1. Union

   • The union of two regular languages A and B, denoted as A ∪ B, includes all strings that are in A, in B, or in both.
   • Regular languages are closed under union, meaning the union of two regular languages is also a regular language.
   • The union can be represented using finite automata by creating a new start state that transitions to the start states of both automata for A and B.

2. Concatenation

   • The concatenation of two regular languages A and B, denoted as A · B, consists of all strings formed by taking a string from A followed by a string from B.
   • Regular languages are closed under concatenation, ensuring that the result is also a regular language.
   • Concatenation can be visualized in finite automata by connecting the accepting states of the automaton for A to the start state of the automaton for B.

3. Kleene Star

   • The Kleene star operation applied to a regular language A, denoted as A*, includes all strings that can be formed by concatenating zero or more strings from A.
   • Regular languages are closed under the Kleene star, meaning the result is also a regular language.
   • The Kleene star allows for the representation of languages that include the empty string and any number of repetitions of strings from A.

4. Intersection

   • The intersection of two regular languages A and B, denoted as A ∩ B, includes all strings that are in both A and B.
   • Regular languages are closed under intersection, meaning the intersection of two regular languages is also a regular language.
   • Intersection can be implemented using finite automata by constructing a product automaton that simulates both original automata simultaneously.

5. Complement

   • The complement of a regular language A, denoted as A', consists of all strings over the alphabet that are not in A.
   • Regular languages are closed under complement, ensuring that the complement of a regular language is also a regular language.
   • To find the complement, one can switch the accepting and non-accepting states in the finite automaton for A.

6. Difference

   • The difference of two regular languages A and B, denoted as A - B, includes all strings that are in A but not in B.
   • Regular languages are closed under difference, meaning the result is also a regular language.
   • The difference can be expressed using intersection and complement: A - B = A ∩ B'.

7. Reversal

   • The reversal of a regular language A, denoted as A^R, consists of all strings that are the reverse of strings in A.
   • Regular languages are closed under reversal, ensuring that the reversal of a regular language is also a regular language.
   • Reversal can be constructed by reversing the transitions in the finite automaton for A and swapping the start and accepting states.

8. Homomorphism

   • A homomorphism is a mapping from an alphabet to another alphabet that transforms strings in a regular language according to specific rules.
   • Regular languages are closed under homomorphism, meaning the image of a regular language under a homomorphism is also a regular language.
   • Homomorphisms can be used to generate new languages by replacing symbols in strings with other strings.

9. Inverse Homomorphism

   • The inverse homomorphism is the pre-image of a homomorphism, mapping strings from a target alphabet back to the original alphabet.
   • Regular languages are closed under inverse homomorphism, ensuring that the inverse image of a regular language is also a regular language.
   • This operation allows for the reconstruction of original strings from transformed strings based on the homomorphism.

10. Substitution

    • Substitution involves replacing each symbol in a string from a regular language with a string from another language.
    • Regular languages are closed under substitution, meaning the result of substituting symbols in a regular language is also a regular language.
    • Substitution can be used to create more complex languages by systematically replacing symbols with predefined patterns or strings.