Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

Theory of Computation - 6 (Pumping Lemma)

Posted on Nov. 10, 2017
theory-of-computation-6-pumping-lemma

In this lecture I am going to explain the famous Pumping Lemma and will prove the restrictions of a DFA. DFA is the very first level and there are many things we cannot do with a DFA. I will explain the Pumping Lemma very elegantly so that you can quickly grasp the concept.

Suppose someone has told you that she has built a DFA that accepts the Set of Binary Strings of the format 0^n 1^n

0^n = n consecutive 0s

1^n = n consecutive 1s

Therefore, the Set contains all such Binary strings where first half of the symbols are all 0s and second half of the symbols are all 1s and number of 0s and number of 1s are equal.

You then ask her how many states are there in the DFA that she has constructed to only accept such strings.

Suppose her answer is 28 states.

Then you give her the string 0^28 1^28 and tell her to take this as an input into her DFA and ask her where is the first loop occurring and how many 0s are there in the loop.

what Loop ??

Well, imagine a simple DFA with 2 states. You give the string 0^2 1^2 as input to this DFA.

0011 is the input string. When the DFA reads the first 0, it either stays on the starting state or go to the 2nd state.

If it stays on the starting state then that is the very first loop. Why ? Because - if you see a symbol and do not change your state, it means that you have looped into the same state.

If it goes to the second state, then when it reads the second 0 in that state - it either stays in the second state which means it has looped into the second state OR it will come back to the first state. If it comes back to the first state then also we get the loop like first state ---> second state ---> first state

Therefore, for her DFA with 28 states, if you give 0^28 1^28 as input string to that DFA, it would definitely have a loop when it is chewing the 28 zeroes. Ask her the length of the very first loop. (Note that her DFA may have many loops while chewing up the 28 zeroes but it would have atleast one loop which we are very sure about)

Say - she has told you that the length of the very first loop is 3.

Now, give her the string 0^31 1^28 as an input to her DFA and her DFA would also accept this string. Why? Because you can pump the very first loop to chew up these 3 additional 0s.

In her DFA the first loop will look like as shown below.

Therefore, this loop can consume the 3 additional 0s that we have put in the input string and can come back to the same state.

Therefore, the DFA is accepting some additional strings which it should not accept. Apart from accepting the strings of the format 0^n 1^n, it is also accepting strings where number of 0s are more than number of 1s. Therefore, the DFA is faulty.

In reality there cannot be any such DFA that accepts Set of Binary Strings of the format 0^n 1^n

Pumping Lemma

We will now define the Pumping Lemma. Definitions are actually written in formal language. But you can understand it more clearly when you meet someone who has built a DFA to accept strings of the format 0^n 1^n and have a dialogue with them.

Before defining the Lemma, let me tell you there is an another way to say the below line

DFA accepts a Set of strings

Another way - DFA accepts the language L, where the language L represents all the strings which are there in the Set.

Therefore, if a language L is accepted by a DFA - we call that language L a Regular Language. (Note - the word language has nothing to do with a programming language, it's just an alternative to replace the word Set)

Pumping Lemma Definition - If L is regular Language (Set) and if the DFA which accepts L (and nothing else) has N number of states, then for all strings Z that belongs to the Language(Set) and which has length >=N, we can split Z in three parts V,W and X where V is the number of symbols before the first loop, W is the number of symbols in the first loop and X is the number of symbols after the first loop and number of symbols in W (first loop) is atleast 1 and (number of symbols in V + number of symbols in W) <= N

Basically the below conditions

Z = VWX

where - |Z|>=N and |W|>=1 and

|VW|<=N (The first Loop has to occur in the first N symbols which we have seen in the dialogue. Just writing it formally)

Therefore, if the above conditions are satisfied then According to Pumping Lemma, DFA must also accept the string V(W^i)X where i>=0

Let Z = 00101110

and V = 001 and W = 01 and X =110

Then the DFA must also accept 0010101110, 001010101110...etc. and Also ACCEPT 001110 ( See i>=0 which means we can remove the W symbols and and the DFA must accept the string with remaining symbols).

If you find it difficult to understand this formal definition, go back to the Dialogue we had in the beginning of the Lecture and correlate that with this formal definition.

In the Dialogue, we used the Pumping Lemma to pump up the first loop to produce some strings which must be accepted by the DFA and DFA end up accepting something which it should not accept.

Therefore, the Pumping Lemma is a very useful tool to check the validity of Deterministic Finite State machines. In the next lecture we will see more applications of the Pumping Lemma. Stay tuned.

previous Lecture DFA closure properties next Lecture Palindromes are not Regular

Sharing is Caring!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2016
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates