# Regular sets and their properties in Theory of Computation

Here, we are going to learn about the **regular sets and their properties in theory of computation**.

Submitted by Mahak Jain, on November 14, 2018

**Any set that denotes the value of the Regular Expression is called a "Regular Set".**

Regular sets have various properties:

**Property 1) The union of two regular sets is also a regular set**

**Proof:**

Let there be two regular expressions RE1 = 0(00)* and RE2 = (00)* So, L1 = {0, 000, 00000,..} (odd length strings without Null) and L2 ={ ε, 00, 0000, 000000,.......} (even length stringswith Null) L1 ∪ L2 = { ε, 0, 00, 000, 0000, 00000, 000000,.......} (all possible lengths stringswith Null) RE (L1 ∪ L2) = 0* (this is also a regular expression or a regular set)

**Hence, proved.**

**Property 2) The intersection of two regular set is also a regular set.**

**Proof:**

Let there be two regular expressions RE1 = 0(0*) and RE2 = (00)* So, L1 = { 0,00, 000, 0000, ....} (odd length strings without Null) L2 = { ε, 00, 0000, 000000,.......} (even length strings with Null) L1 ∩ L2 = { 00, 0000, 000000,.......} (even length stringswithout Null) RE (L1 ∩ L2) = 00(00)*(this is a regular set or regular expression also).

**Hence, proved.**

**Property 3) The complement of a regular set is also regular set.**

**Proof:**

Let there be a regular expression − RE = (00)* So, L = {ε, 00, 0000, 000000, .......} (even length stringswith Null) Complement of L is set of all the strings that is not included in L. So, L' = {0, 000, 00000, .....} (odd length stringswithout Null) RE (L') = 0(00)*this denotes a regular set or regular expression in itself.

**Hence, proved.**

**Property 4) The difference of two regular set is also a regular set.**

**Proof:**

Let there be two regular expressions − RE1 = 0 (0*) and RE2 = (00)* So, L1 = {0, 00, 000, 0000, ....} (all possible lengths stringswithout Null) L2 = { ε, 00, 0000, 000000,.......} (even length strings with Null) L1 – L2 = {0, 000, 00000, 0000000, ....} (all odd lengths strings without Null) RE (L1 – L2) = 0 (00)*(this is also a regular set or a regular expression in itself)

**Hence, proved.**

**Property 5) The reversal of a regular set is also a regular set.**

**Proof:**

If L is a regular set: Let, L = {ab, ba, bb, ba} RE (L) = b1 + 1b +bb + ba LR = {ba, ab, bb, ab} RE (LR) = ab + ba + bb + bathis is the reverse and also a regular set or a regular expression in itself

**Hence, proved.**

**Property 6) The closure of a regular set or an expression is also a regular set.**

**Proof:**

If L = {0, 000, 00000, .......} (all odd length strings without Null) i.e., RE (L) = 0 (00)* L* = {0, 00, 000, 0000 ,00000,……………} ( all lengths strings without Null) RE (L*) = 0 (0)*(this is also a regular set or a regular expression)

**Hence, proved.**

**Property 7) The concatenation of two regular sets is also a regular set.**

**Proof:**

Let RE1 = (a+1)*a and RE2 = a1(a+1)* Here, L1 = {a, aa, 1a, aaa, a1a, ......} (Set of strings ending in a) and L2 = {a1, a1a,a11,.....} (Set of strings beginning with a1) Then, L1 L2 = {aa1,aa1a,aa11,aaa1,aa1a,aaa11,1aa1,1aa1a,.............} Set of strings containing aa1 as a substring which can be denoted by an RE − (a + 1)*aa1(a + 1)*

**Hence, proved.**

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions