DSAAT BLOG ( GROUP 4 )

  

Regular Expression and its Closure Properties

First of all let's see What is Regular Expression ?

               Regular Expression which is also referred as rational expression , is a sequence of characters that specifies a search pattern. A regular expression is an algebraic formula whose value is a pattern consisting of a set of strings, called the language of the expression.

or

               The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language.  

 

 

• A regular expression can also be described as a sequence of pattern that defines a string. And these expressions are used to match character combinations in strings. 
• The languages accepted by finite automata are referred to as Regular languages. String searching algorithm used this pattern to find the operations on a string.

Above we use a term "Automata" so now question arises What is automata ?

                The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.

• Theory of automata is a theoretical branch of computer science and mathematical. It is the study of abstract machines and the computation problems that can be solved using these machines. The abstract machine is called the automata. 

Now Continuing to regular expressions :

                Regular expressions can be thought of as the algebraic description of a regular language.There are some properties for regular language which are known as closure properties and they are as follows:

Closure Properties : Closure properties on regular languages are defined as certain operations on regular langauge which are guranteed to produce regular langauge .

Closure refers to some operation on a language, resulting in a new language that is of same "type" as originally operated on i.e., regular.

Regular languages are closed under following operations :

• Union

The Union of two regular expressions is also a regular expression.

L1 U L2 = { s | s is in L1 or s is in L2 } 

Example :-

L1 = {an | n > O} and L2 = {bn | n > O}

L3 = L1 U L2 = {an U bn | n > O} is also regular expression. 

• Intersection

If L1 and L2 are two regular languages then their intersection is also an intersection.

L1 ⋂ L2 = { st | s is in L1 and t is in L2 }

Example :-

L1= {am bn | n > 0 and m > O} and

L2= {am bn U bn am | n > 0 and m > O}

L3 = L1 ∩ L2 = {am bn | n > 0 and m > O} are also regular expression. 

• Kleen Closure

If L is a regular language then its Kleen closure L1* will also be a regular language. The iteration (or closure) of a regular expression is also a regular expression.

L* = Zero or more occurence of language L 

Example :-

L1 = (a U b )

L1* = (a U b)* 

Note that a* means zero or more occurrence of a in the string while a+ means that one or more occurrence of a in the string. That means a* denotes language L = {є , a, aa, aaa, ….} and a+ represents language L = {a, aa, aaa, ….}. And also note that there can be more than one regular expression for a given set of strings. 

•  Concatenation

If L1 and If L2 are two regular languages, their concatenation L1.L2 will also be regular. 

Example :-

L1 = {an | n > 0} and L2 = {bn | n > O}

L3 = L1.L2 = {am . bn | m > 0 and n > O} is also regular.

•  Complement

If L(G) is a regular language, its complement L'(G) will also be regular. Complement of a language can be found by subtracting strings which are in L(G) from all possible strings.

Example

L(G) = {an | n > 3} L'(G) = {an | n <= 3}

•  Reversal 

If L = { 0 , 01 , 100 } is regualr then  = { 0 , 10 , 001 } will also be regular.

•  Homomorphism

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

If L is a regular language, and h is a homomorphism on its alphabet, then h(L) = {h(w) | w is in L} is also a regular language.

•  Inverse Homomorphism

The inverse homomorphism theorem states that if h is a homomorphism from alphabet ? to alphabet A and L is a regular language on A then h’(L) is also a regular language

Examples :

Find Regular Expressions for following : 

1) { 1 , 2 , 3 }

R.E. =  1 + 2 + 3                              1 or 2 or 3 

 

        

2) { ^ , ab }

R.E. =  ^ ab

3) { abb , a , b , bba }

R.E. =  abb + a + b + bba                 abb or a or b or bba 

4) { ^  , 0 , 00 , 000 , ..... }

R.E. =  0*                                        closure of 0 

5) { 1 , 11 , 111 , 1111 , ..... }

R.E. =  1^+   

 

6) Write the regular expression for the language accepting all the string which are starting with 1 and ending with 0, over ∑ = {0, 1}.

Solution :

In a regular expression, the first symbol should be 1, and the last symbol should be 0. The r.e. is as follows:

R.E. = 1(1+0)*0 

 

7) Write the regular expression for the language starting with a but not having consecutive b's. 

Solution :

The regular expression has to be built for the language:

L = { a , aba , aab , aba , aaa , abab , .... } 

The regular expression for the above language is:

R.E. = { a + ab }*

 

8) Write the regular expression for the language over ∑ = {0} having even length of the string.

Solution : 

The regular expression has to be built for the language :

L = { ε , 00 , 0000 , 000000 , ....... }

The regular expression for the above language is: 

R = (00)*

 

By This we conclude our Blog. Hope you enjoy reading. Thank You.