2.6 Closure properties of regular languages

Regular languages have cool properties that let us combine them in different ways. We can mix and match them using union, concatenation, and star operations, and the result is always another regular language.

These closure properties are super useful for building new regular languages from existing ones. We can create more complex languages by repeatedly applying these operations, expanding our toolkit for working with regular languages.

Closure Properties of Regular Languages

Union, Concatenation, and Star Operations

Top images from around the web for Union, Concatenation, and Star Operations

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

1 of 3

Top images from around the web for Union, Concatenation, and Star Operations

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

• 

  CS664 - Formal Language Theory View original

  Is this image relevant?

1 of 3

• Regular languages are closed under the union operation
  • If L1 and L2 are regular languages, then their union L1 ∪ L2 is also a regular language
  • Example: If L1 = {a, b} and L2 = {b, c}, then L1 ∪ L2 = {a, b, c}
• Regular languages are closed under the concatenation operation
  • If L1 and L2 are regular languages, then their concatenation L1 · L2 is also a regular language
  • Example: If L1 = {a, b} and L2 = {c, d}, then L1 · L2 = {ac, ad, bc, bd}
• Regular languages are closed under the Kleene star operation
  • If L is a regular language, then L* (the Kleene star of L) is also a regular language
  • L* represents zero or more concatenations of strings from L
  • Example: If L = {a, b}, then L* = {ε, a, b, aa, ab, ba, bb, aaa, ...}

Proving Closure Properties

• The closure properties can be proved using the equivalence between regular languages and finite automata
• The constructed automata for the union, concatenation, and star operations accept the corresponding languages
• The proofs involve constructing new finite automata that accept the languages resulting from the operations applied to the original regular languages
  • For the union operation, a new automaton is constructed with a new initial state and transitions to the initial states of the automata for L1 and L2
  • For the concatenation operation, a new automaton is constructed by adding an ε-transition from each final state of the automaton for L1 to the initial state of the automaton for L2
  • For the Kleene star operation, a new automaton is constructed with a new initial state, an ε-transition from the new initial state to the initial state of the automaton for L, and ε-transitions from each final state back to the initial state

Applying Closure Properties

Constructing New Regular Languages

• The closure properties of regular languages can be used to construct new regular languages by applying union, concatenation, and star operations to existing regular languages
• Given regular languages L1 and L2:
  • The union of L1 and L2 (L1 ∪ L2) can be constructed by creating a new regular language that accepts all strings that are in either L1 or L2
  • Example: If L1 = {a, b} and L2 = {b, c}, then L1 ∪ L2 = {a, b, c}
• Given regular languages L1 and L2:
  • The concatenation of L1 and L2 (L1 · L2) can be constructed by creating a new regular language that accepts all strings formed by concatenating a string from L1 with a string from L2
  • Example: If L1 = {a, b} and L2 = {c, d}, then L1 · L2 = {ac, ad, bc, bd}
• Given a regular language L:
  • The Kleene star of L (L*) can be constructed by creating a new regular language that accepts all strings formed by concatenating zero or more strings from L
  • Example: If L = {a, b}, then L* = {ε, a, b, aa, ab, ba, bb, aaa, ...}

Repeated Application of Closure Properties

• Closure properties can be applied repeatedly to construct more complex regular languages from simpler ones
• Example: Given regular languages L1 = {a, b} and L2 = {c, d}:
  • Construct L3 = L1 ∪ L2 = {a, b, c, d}
  • Construct L4 = L1 · L2 = {ac, ad, bc, bd}
  • Construct L5 = L3* = {ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd, ...}

Regularity of Constructed Languages

Guaranteed Regularity

• When a language is constructed by applying union, concatenation, or star operations to regular languages, the resulting language is guaranteed to be regular due to the closure properties
• If a language is constructed using only union, concatenation, and star operations applied to regular languages, then the resulting language is guaranteed to be regular
• Example: If L1 and L2 are regular languages, then L1 ∪ L2, L1 · L2, and L1* are all guaranteed to be regular languages

Determining Regularity

• To determine if a language constructed from regular languages is regular, one can analyze the operations applied to the regular languages and use the closure properties to conclude that the resulting language is regular
• Example: Given regular languages L1 = {a, b} and L2 = {c, d}, the language L3 = (L1 ∪ L2)* is regular because:
  • L1 and L2 are regular languages
  • The union of L1 and L2 is a regular language (closure under union)
  • The Kleene star of a regular language is a regular language (closure under star)

Non-Regular Constructed Languages

• If a language is constructed using operations other than union, concatenation, and star, or if the operands are not regular languages, then the resulting language may not be regular
• Further analysis would be required to determine the regularity of such languages
• Example: If L1 is a regular language and L2 is a non-regular language, then the language L3 = L1 ∩ L2 (intersection) may not be regular, as regular languages are not closed under intersection