Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Closure Properties of regular languages
3.
Union
4.
Concatenation
5.
Intersection 
6.
Reversal
7.
Difference
8.
Complementation
9.
Homomorphism
10.
Inverse Homomorphism
11.
Frequently Asked Questions
11.1.
What are closure properties of regular languages?
11.2.
What is regular language properties?
11.3.
Are regular languages closed under closure?
12.
Conclusion
Last Updated: Mar 27, 2024
Easy

Closure Properties of a Regular language

Author Sinki Kumari
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

 

Introduction

In this blog, we will learn about the closure properties of a regular language. But before discussing closure and its properties, we should first understand what a regular language is.

A regular language may be expressed using regular expressions, non- deterministic or deterministic finite automata, or state machines. A language is a collection of strings composed of characters from a specific alphabet or set of symbols. Regular languages are a subset of the entire string set.

Closure properties of a regular language

 

 Regular languages are one of the first ideas taught in computability classes and are utilized in parsing and developing programming languages. These are important for assisting computer scientists in seeing patterns in data and grouping specific computational issues together; once this is done, they may utilize comparable methodologies to address the problems that have been grouped. In computability theory, regular languages are an essential issue.

Compiler Design

Also see, Regular Languages and Finite Automata

Closure Properties of regular languages

When we talk about groups of objects, we use "Closure." If we have two regular languages, L1 and L2, and L is generated by performing specific operations on L1 and L2, then L is also regular.

Let us consider an example; let us take a confectionery set. Each component of the set contains a different type of candy. What happens if we take a candy from the set candy and drop it on the clean ground? We can still eat it. Thus it qualifies as candy. The set candy is closed using the "drop" method.

Closure properties used in Regular languages are as follows:

  1. Union
  2. Concatenation
  3. Intersection
  4. Reversal
  5. Difference
  6. Complementation
  7. Homomorphism
  8. Inverse Homomorphism
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Union

Statement: If L1 and L2 are regular languages, then their union L1 U L2 is also a regular language. 

Proof: Let M1 and M2 be two finite Automata that accept the L1 and L2 regular languages, respectively. If we wish to demonstrate that the union of L1 and L2 is likewise a regular language, we may do the following:

 

  1. Make a new starting point.
  2. Make ?-transitions from the new state to each of M1 and M2's original states.
union

 

Concatenation

Statement: Concatenation of two regular languages is also regular. 

Proof: Let M1 and M2 be two finite automata, and L1 and L2 be the languages that M1 and M2 accept, respectively. We aim to demonstrate that L1L2 = L, i.e., their concatenation yields regular language. Let M be a finite automaton composed of M1 and M2.
Concatenation

Intersection 

Statement: If L and M are regular languages, then L ∩ M is also.

Proof: Assume L1 and L2 are regular languages, and we wish to demonstrate that the intersection of L1 and L2 is likewise a regular language. De Morgen's Law may be used to calculate the intersection of languages L1 and L2.

Intersection

Reversal

Statement: Under reversal, the set of regular languages is closed.

Proof: Let M be a deterministic finite automaton that accepts L; we will create M' from M so that M and M' states are the same. Make the final state of M the accepting state of M' and the final state of M the beginning state of M'. The direction of the edges in M' has been reversed. It denotes that the string has been written backward, i.e., the reverse of abbc is cbba.

Difference

Statement: If L1 and L2 are regular languages, then L1-L2 is as well, which implies all the strings in L1 but not in L2.

Proof: Since L2 is regular, its complement L2' is also regular, and L1? L2' too is regular; this proves that L1-L2 is also regular.

Complementation

Statement: According to the theorem, the complement of two regular languages is also regular.

Proof: If M is a deterministic finite automaton that accepts L, we may write L= L(M), then L' = L. (M1). The DFA M1 is similar to M, except that M's accepting states are now M1's non-accepting states and vice versa.

Homomorphism

A function that returns a string for each symbol in an alphabet is a homomorphism.

Statement: If L is a regular language and h is an alphabet homomorphism, then h(L) = h(w) | w is in L is also a regular language.

Proof: Assume E is a regular expression for L. Apply h for each symbol in E. The language of the resultant RE is h (L).

Inverse Homomorphism

Statement: If h is a homomorphism from the alphabet? To alphabet A and L is a regular language on A, then h' (L) is likewise regular.

Also See, Specifications of Tokens in Compiler Design

Frequently Asked Questions

What are closure properties of regular languages?

Regular languages are closed under complement, union, intersection, concatenation, Kleene star, reversal, homomorphism, and substitution.

What is regular language properties?

Regular languages have finite state machines, represent simple patterns, are closed under union, intersection, concatenation, and Kleene star operations.

Are regular languages closed under closure?

Yes, regular languages are closed under the closure operation, meaning their complement is also a regular language.

Conclusion

This article discussed the closure properties of regular languages. I hope you have gained some insight into this topic of closure properties.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Previous article
Lexer and Lexer Generators
Next article
Context-free Grammars
Live masterclass