Theory of Automata

Intro. To Theory of Automata

Finite Automata

Moore and Mealy Machine

Regular Expressions

Derivation in Automata

Context Free Language

Turing Machine

Closure Properties of Regular Languages

Closure properties on regular languages are defined as

Closure is nothing but an operation which is performed on a language, and then the new resulting language will be of same “type” as original language.

Thus,

If closure operations are performed on some regular languages then the result will also be the regular language.
if the resultant language after closure-operation is still a regular language then it holds the closure property under that operation

General Example

Suppose N is set of natural numbers i.e N= {1,2,3….infinity}. if we apply addition on any two or more numbers then result will be in set N. So, the addition operation is called closure property of set N.
Now suppose subtraction of any two numbers i.e. 5-12 =-7. The result -7 is not a value of set N. So, Here subtraction does not hold the closure property of set N.

Regular languages are closed under following operations

1. Kleene Closure

Let R is regular expression whose language is L. Now apply the Kleene closure on given regular expression and language. So, R* is a regular expression whose language will become L*.

Example

Suppose R= (a) then its language will be L= {a}. Now apply Kleene Closure on given regular expression and language,

if R* = (a)* then its language will be L* = {e, a, aa, aaa, aaaa….}

So, L* is still a regular language. Thus Kleene clouser is satisfied.

2. Positive Closure

R is a regular expression whose language is L.R⁺is a regular expression whose language is L⁺

Example

Suppose R= (a) then its language will be L= {a} . Now apply positive Closure on given regular expression and language,

if R⁺ = (a)⁺ then its language will be L⁺ = {a, aa, aaa, aaaa….}

So, L⁺ is still a regular language. Thus positive clouser is satisfied.

3. Complement

The complement of a language L is (Σ* – L). Where sigma (Σ) holds the input symbols use for generating the language. So, complement of a regular language is always regular.

4. Union

Let L1 and L2 be the languages of regular expressions R1 and R2, respectively. Then R1+R2 (R1 U R2) is ALSO a regular expression whose language is L3 = (R1 U R2). L3 also belongs to regular language

5. Concatenation

Let L1 and L2 be the languages of regular expressions R1 and R2, respectively. Then R1.R2 is ALSO a regular expression whose language is L3 = (R1.R2). L3 also belongs to regular language

6. Intersection

Let L1 and L2 be the languages of regular expressions R1 and R2, respectively then the it a regular expression whose language is L1 intersection L2.

7. Set Difference Operator

Let L1 and L2 be the languages of regular expressions R1 and R2, respectively then it a regular expression whose language is L1 – L2.= strings in L1 but not L2.

8. Reverse Operator

Given language L, L^Ris the set of strings whose reversal is in L.
Example: L = {0, 01, 100};
L^R ={0, 10, 001}.
L^Rstill a regular language

9. Quotient Operation

It is operation like division.

Note: if L1 ={11} and L2= {10} then L1/L2 =ebsilon (e). Because divider should be completely cut from either left (in left quotient) or right (in right quotient). If divider is not completely cut from either left (in left quotient) or right (in right quotient) then result will be ebsilon (e).

If string of L1 and L2 are exactly same then result will also in ebsilon (e). i.e. 10/10= ebsilon (e).

Let explain with example

Let L1= {10, 100, 1010, 101110}
L2= {10}

Let explain left quotient

L1/L2 (left)= {10/10, 100/10, 1010/10, 101110/10} = {e,0,10,1110}

Let explain right quotient

L1/L2 (right)= {10/10, 100/10, 1010/10, 101110/10} = {e,e,10,1011}

So, above resultant {e,e,10,1011} is also a regular language because finite automata is possible.

Note: if L1 contains 3 strings and L2 contains 2 strings then Take one string from L2 and divide on all L1 string. After that, Take second string from L2 and divide on all L1 strings.

10. INIT Operation

INIT is also called initial or prefix. If a language is given with N number of strings then find the prefix of each string. By combining the all prefix of all strings, new language is generated. New generated language is INIT language which is still a regular language.

Method to calculate INIT

INIT of any string is start with epsilon. Then start from left most and consider only first character. In the next, consider first two character. Then first three and so on until the length of string is equal to length of prefix.

Consider a string is “abcd” of any language then its prefix is given below

Prefix of String “abcd” = {e, a, ab, abc, abcd}

Example 01

Consider a Regular language (L)={ab, ba}.

Prefix of String “ab” = {e, a, ab}
Prefix of String “ba” = {e, b, ba}

New language after INIT = combination of all prefix of all strings = {e,a,b,ab,ba}

11. Homomorphism

It is use to substitute (replace) the value of sigma with given delta values. Delta is nothing but a symbol. Delta contains some values which are used to replace the sigma values.

Suppose “H” is delta then we can say

H(L) = {H(w) | w ∈L}

Example

If L = {00, 101} and H(0) = “aa” and H(1) = “bb” then after substitution H(L) is given below

H(L) = {aaaa,bbaabb}

Note: in above example “0” is replace with “aa” and “1” is replace with “bb” in given language.

Ebsilon will remain the same if no substitution for ebsilon is given

12. Inverse Homomorphism

It is the also a substitution technique like homomorphism but functionality of substitution is opposite. It replace the value of Delta with sigma values. It is denoted by power of -1 i.e (H^-1)

Example 01

Suppose “H” is delta then we can say

If L = {aabb} and H(0) = “aa” and H(1) = “bb” then after substitution H^-1(L) is given below

H^-1(L) = {01}