Decision Properties of Regular Languages

The decision algorithm for regular sets requires the following points to be remembered:

a. An algorithm must always terminated to be called an algorithm. Basically, an algorithm needs to have the following four characteristics:

i. An algorithm must be written using a finite number of unambiguous steps.

ii. For every possible input, only a finite number of steps are to be performed, and the algorithm is supposed to produce a result.

iii. Every time, the same and correct result is to be produced for the same input.

iv. Each step of the algorithm must have the properties as explained in (i), (ii), (iii).

 

b. A regular language is just a set of strings over a finite alphabet. Every regular set can be represented by a regular expression and accepted by a minimum state DFA.

We choose DFAs represented by usual notational so that we can analyses every DFA and even simulate them.

The type of questions we are concerned are such as:

i. Is the given language empty, finite or infinite?

ii. Is one regular set equivalent to another?

and so on. Now we have to establish an algorithm to answer such questions. For our purpose we use that regular sets are represented by finite automata.

Pumping Lemma

Pumping Lemma for Regular Languages

The language accepted by the finite automata is called Regular Language. If we are given a language L and asked whether it is regular or not? So, to prove a given Language L is not regular we use a method called Pumping Lemma.

The term Pumping Lemma is made up of two words:

1. Pumping: The word pumping refers to generate many input strings by pushing a symbol in an input string again and again.
2. Lemma:  The word Lemma refers to intermediate theorem in a proof.

Pumping Lemma is used to prove that given language is not regular. So, first of all we need to know when a language is called regular. A language is called regular if:

• Language is accepted by finite automata.
• A regular grammar can be constructed to exactly generate the strings in a language.
• A regular expression can be constructed to exactly generate the strings in a language.

Principle of Pumping Lemma

The pumping lemma states that all the regular languages have some special properties. If we can prove that the given language does not have those properties, then we can say that it is not a regular language.

Theorem 1: Pumping Lemma for Regular Languages

If L is an infinite regular language then there exists some positive integer n (pumping length) such that any string w ? L has length greater than or equal to n. i.e. |w| >=n, then string can be divided into three parts, w=xyz satisfying the following condition:

• For each i>=0, xyiz ? L.
• |y| > 0
• |xy| <= n

|w| represents the length of string w and yimeans that i copies of y are concatenated together, y0 = ?.

Applying Pumping Lemma

We will use above theorem to prove that given language is not regular. The steps needed to prove that given languages is not regular are given below:

Step1: Assume L is a regular language in order to obtain a contradiction. Let n be the number of states of corresponding finite automata.

Step2: Now chose a string w in L that has length n or greater

i.e.  |w| >= n. use pumping lemma to write

w = xyz with |xy| <= n and |y| = 0.

Step3: Finally demonstrate that we cannot pumped by considering all ways of dividing w into x, y and z, and for each such division find a value of I such that xyiz ? L. This contradicts our assumption; hence L is not regular.

We prove xyiz ? L by considering the length of xyz i.e. |xyiz| or by using the structure of strings in L.

Example

Let L= { anbn | n>=0 }. By using pumping lemma show that L is not regular language.

Solution:

Step1: Assume L is a regular language in order to obtain contradiction. Let n be the number of states in finite automata accepting L.

Step2: Let w = anbn,  then |w| = 2n > n. Using pumping lemma, we can demonstrate w in three parts of xyz such that w = xyz with |xy| <=n and |y| > 0.

Step3: Now we want to find i, xyiz ? L.

There are three possibilities for y, we will consider all cases one by one and show that given language contains some string not for { anbn | n>=0 }.

Case 1: The string y consists of only a’s i.e. y = ak  (k>=1).

We have w = xyz

                w = anbn

In given language we have equal numbers of a’s and b’s w ? L so it must satisfy this condition. Let us take i=0.

As            xyz = anbn

                xz   = an-kbn

               n-k ? n

So xz ? L. This case is a contradiction.

Case 2: The string y consists of only b’s i.e. y = bm  (m >= 1).

We have w = xyz

                w = anbn

In given language, we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=0.

As            xz = anbn-m

                xz   = an-kbn

Where      n ? m

So xz ? L. This case also gives contradiction.

Case 3: The string y consists of both a’s and b’s i.e. y = akbm  (k,m >= 1).

We have w = xyz

                w = anbn

                w = an-kakbm bn-m

In given language we have equal number of a’s and b’s w ? L, so it must satisfy this condition. Let us take i=2.

                xy2z = xyyzi

                        = an-kakbmkbm bn-m

In this case, the string xyyz must have equal number of a’s and b’s but they are out of order with some b’s before a’s. Hence it is not a member of L. which contradicts our assumption.

Thus, in all cases we get a contradiction. Therefore, L is not regular.

Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.

• If L is regular, it satisfies Pumping Lemma.

• If L does not satisfy Pumping Lemma, it is non-regular.

Example:

Prove that L = {aibi | i ≥ 0} is not regular.

Solution −

• At first, we assume that L is regular and n is the number of states.

• Let w = anbn. Thus |w| = 2n ≥ n.

• By pumping lemma, let w = xyz, where |xy| ≤ n.

• Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.

• Let k = 2. Then xy2z = apa2qarbn.

• Number of as = (p + 2q + r) = (p + q + r) + q = n + q

• Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.

• Thus, xy2z is not in L. Hence L is not regular.

Example 3:

Solution:

L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10^p10^p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10^aand y = 0^b and z = 0^p-a-b10^p, for b ≥ 1.
(a) x = " and y = 10b and z = 0^p-b10^p1.
Choose i = 2. We need to show that xy²z is not in L2.
In case (a), xy2z = 10^p+b10^p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10^b10^p10^p, which is not in L2 because it contains three 1’s.

Example 4:

We prove that L3 = {1ⁿ² | n ≥ 0} is not regular.
Solution:
We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1^p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1^a and y = 1^b and z = 1^p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy²z = 1^n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 

Example 5:

Prove that Language L = {0n: n is a perfect square} is irregular.
Solution: 

L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xy^kz is also in L.
Choose w to be w = 0s where s = n² that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n² in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n²- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n²- k ) + 2k = n² + k where n² + k < 1 =" (n+1)(n+1)"> n² (As k > 0)
=> n² <>2 + k < (n+1)2 => n² + k is not a perfect square
=> xy²z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.

Closure properties of Regular languages

In an automata theory, there are different closure properties for regular languages. They are as follows −

• Union
• Intersection
• concatenation
• Kleene closure
• Complement

Let see one by one with an example

Union

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

Example

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

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

Intersection

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

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.

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.

Kleene Closure

If L1 is a regular language, its Kleene closure L1* will also be regular.

Example

L1 = (a U b )

L1* = (a U b)*

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}

Note − Two regular expressions are equivalent, if languages generated by them are the same. For example, (a+b*)* and (a+b)* generate the same language. Every string which is generated by (a+b*)* is also generated by (a+b)* and vice versa.

Decision Properties:

Approximately all the properties are decidable in case of finite automaton.

(i) Emptiness 
(ii) Non-emptiness 
(iii) Finiteness 
(iv) Infiniteness 
(v) Membership 
(vi) Equality  

These are explained as following below.

(i) Emptiness and Non-emptiness:

• Step-1: select the state that cannot be reached from the initial states & delete them (remove unreachable states).
• Step 2: if the resulting machine contains at least one final states, so then the finite automata accepts the non-empty language.
• Step 3: if the resulting machine is free from final state, then finite automata accepts empty language.

  (ii) Finiteness and Infiniteness:

  • Step-1: select the state that cannot be reached from the initial state & delete them (remove unreachable states).
  • Step-2: select the state from which we cannot reach the final state & delete them (remove dead states).
  • Step-3: if the resulting machine contains loops or cycles then the finite automata accepts infinite language.
  • Step-4: if the resulting machine do not contain loops or cycles then the finite automata accepts infinite language.
  (iii) Membership:
  Membership is a property to verify an arbitrary string is accepted by a finite automaton or not i.e. it is a member of the language or not.

  Let M is a finite automata that accepts some strings over an alphabet, and let ‘w’ be any string defined over the alphabet, if there exist a transition path in M, which starts at initial state & ends in anyone of the final state, then string ‘w’ is a member of M, otherwise ‘w’ is not a member of M.

  (iv) Equality:
  Two finite state automata M1 & M2 is said to be equal if and only if, they accept the same language. Minimise the finite state automata and the minimal DFA will be unique.

Arden's Theorem

Arden's Theorem

You can use Arden’s Theorem to find out a regular expression of a Finite Automaton with the properties of regular expressions.

Statement −

Let’s assume that P and Q be two regular expressions.

Incase if P does not include a null string, then R = Q + RP has a unique solution that is R = QP*

Proof −

 [After putting the value R = Q + RP]

= Q + QP + RPP

If you include the value of R recursively repetitively then you will get the following equation −

It’s proved.

Assumptions for Applying Arden’s Theorem

• The transition diagram must not have NULL transitions
• It must have only one initial state

Method

Step 1 – Now create equations in the below mentioned form for all the states of the DFA having n states with initial state q1.

q1 = q1R11 + q2R21 + … + qnRn1 + ε

q2 = q1R12 + q2R22 + … + qnRn2

…………………………

…………………………

…………………………

…………………………

qn = q1R1n + q2R2n + … + qnRnn

Rij represents the set of labels of edges from qi to qj, if no such edge exists, then Rij = ∅

Step 2 − Solve these equations to get the equation for the final state in terms of Rij

Example:

Construct a regular expression corresponding to the automata given below −

Solution −

Here the initial state and final state is q1.

The equations for the three states q1, q2, and q3 are as follows −

q1 = q1a + q3a + ε (ε move is because q1 is the initial state0

q2 = q1b + q2b + q3b

q3 = q2a

Now, we will solve these three equations −

q2 = q1b + q2b + q3b

= q1b + q2b + (q2a)b (Substituting value of q3)

= q1b + q2(b + ab)

= q1b (b + ab)* (Applying Arden’s Theorem)

q1 = q1a + q3a + ε

= q1a + q2aa + ε (Substituting value of q3)

= q1a + q1b(b + ab*)aa + ε (Substituting value of q2)

= q1(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

Hence, the regular expression is (a + b(b + ab)*aa)*.

Example:

Construct a regular expression corresponding to the automata given below −

Solution −

Here the initial state is q1 and the final state is q2

Now we write down the equations −

q1 = q10 + ε

q2 = q11 + q20

q3 = q21 + q30 + q31

Now, we will solve these three equations −

q1 = ε0* [As, εR = R]

So, q1 = 0*

q2 = 0*1 + q20

So, q2 = 0*1(0)* [By Arden’s theorem]

Hence, the regular expression is 0*10*.

Example:

Construct the regular expression for the given DFA

Solution:

Let us write down the equations

q1 = q1 0 + ε 

Since q1 is the start state, so ε will be added, and the input 0 is coming to q1 from q1 hence we write
State = source state of input × input coming to it

Similarly,

q2 = q1 1 + q2 1

q3 = q2 0 + q3 (0+1)

Since the final states are q1 and q2, we are interested in solving q1 and q2 only. Let us see q1 first

q1 =  q1 0 + ε

We can re-write it as

q1 = ε + q1 0

Which is similar to R = Q + RP, and gets reduced to R = OP*.

Assuming R = q1, Q = ε, P = 0

We get

q1 = ε.(0)*

q1 = 0*    (ε.R*= R*)

Substituting the value into q2, we will get

q2 = 0* 1 + q2 1

q2 = 0* 1 (1)*   (R = Q + RP  →  Q P*)

The regular expression is given by

r = q1 + q2

= 0^* + 0^* 1.1^*

r = 0^* + 0^* 1⁺    (1.1^* = 1⁺)

PROBLEMS BASED ON CONVERTING DFA TO REGULAR EXPRESSION-

 

Problem-01:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

• A = ∈ + B.1 ……(1)
• B = A.0 ……(2)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (1) in (2), we get-

B = (∈ + B.1).0

B = ∈.0 + B.1.0

B = 0 + B.(1.0) ……(3)

 

Using Arden’s Theorem in (3), we get-

B = 0.(1.0)*

 

Thus, Regular Expression for the given DFA = 0(10)*

 

Problem-02:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

• q1 = ∈ ……(1)
• q2 = q1.a ……(2)
• q3 = q1.b + q2.a + q3.a …….(3)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (1) in (2), we get-

q2 = ∈.a

q2 = a …….(4)

 

Using (1) and (4) in (3), we get-

 

q3 = q1.b + q2.a + q3.a

q3 = ∈.b + a.a + q3.a

q3 = (b + a.a) + q3.a …….(5)

 

Using Arden’s Theorem in (5), we get-

q3 = (b + a.a)a*

 

Thus, Regular Expression for the given DFA = (b + aa)a*

 

Problem-03:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

• q1 = ∈ + q1.b + q2.a ……(1)
• q2 = q1.a + q2.b ……(2)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using Arden’s Theorem in (2), we get-

q2 = q1.a.b* …….(3)

 

Using (3) in (1), we get-

q1 = ∈ + q1.b + q1.a.b*.a

q1 = ∈ + q1.(b + a.b*.a) …….(4)

 

Using Arden’s Theorem in (4), we get-

q1 = ∈.(b + a.b*.a)*

q1 = (b + a.b*.a)*

 

Thus, Regular Expression for the given DFA = (b + a.b*.a)*

 

Problem-04:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

• q1 = ∈ + q1.a + q3.a ……(1)
• q2 = q1.b + q2.b + q3.b ……(2)
• q3 = q2.a …….(3)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (3) in (2), we get-

q2 = q1.b + q2.b + q2.a.b

q2 = q1.b + q2.(b + a.b) …….(4)

 

Using Arden’s Theorem in (4), we get-

q2 = q1.b.(b + a.b)* …….(5)

 

Using (5) in (3), we get-

q3 = q1.b.(b + a.b)*.a …….(6)

 

Using (6) in (1), we get-

q1 = ∈ + q1.a + q1.b.(b + a.b)*.a.a

q1 = ∈ + q1.(a + b.(b + a.b)*.a.a) …….(7)

 

Using Arden’s Theorem in (7), we get-

q1 = ∈.(a + b.(b + a.b)*.a.a)*

q1 = (a + b.(b + a.b)*.a.a)*

 

Thus, Regular Expression for the given DFA = (a + b(b + ab)*aa)*