Archive

logic

No subject is more core to Computer Science than Automata Theory and yet in my humble opinion is the one that many students neglect and despise. If the subject is not properly introduced the majority will find it too abstract, dry and pointless. This combined with the academic requirement of reproducing the formal proofs drains all the sweetness from its study.  And the fact is, yes the subject is abstractness at its glory and yet if approached the right way students can easily give form and structure that they can identify and relate. The same goes with the proofs, and yes there is a lot to deal, the formal language used in the canonical texts usually become abstruse if handled without help. Thus towards the end of the semester students try to vacate as much space in their heads as possible to stuff in the writings of the pioneers in the field, just to flush out the trash on the day of reckoning (end-semester exams :D).

If the above resonates with you in one manner or the other, I guess you are either doing CS or have done CS. With these assumptions let me get straight to the topic, which is an attempt to convey my understanding of ‘Pumping Lemma’ for regular languages. If you think you haven’t really understood the idea behind this method of disproving regularity of a formal language, be happy to give it another try. If otherwise, I hope not to disappoint you and urge you to have a look.

Let me get you into the mood my brushing up the basics.Regular languages are the ones accepted by a Finite Automaton, and are the simplest of the formal languages. Finite automaton are the machines that do not have access to a working memory and are informally defined as a set of states and rules that define transition from one state to another on a particular input. These machines do all their work by jumping from one state to another. A finite automaton constructed for a regular language only accepts strings in that particular language. That is a finite automaton of a regular language decides whether an arbitrary string belongs to the given language. A language is not regular if we cannot design an Finite automaton for it. But trying to prove a language is not regular by failing to come up with an equivalent Finite automaton is futile. Instead methods like the Pumping Lemma are used to bring out characteristics of a language that are contrary to regular languages. I hope this small intro has brought back those forgotten ideas or have reinforced what you have learned. I wish I do write about these in detail in the future.

Before we start to prove certain languages are not regular we need to understand what the pumping lemma is. A lemma by definition is an idea which in itself is not very useful but in conjunction with other ideas can be put to use. The same goes with pumping lemma, which in itself forms the base axiom and is derived from the Pigeon Hole principle. You must have heard about the pigeon hole principle, and probably must have readily discarded it as common sense. And yes it is common sense. If there are m pigeons and n pigeon holes (nests) ,if m>n and all pigeon gets a pigeon hole then it implies that one or more pigeon holes contain more than one pigeon. The same idea when applied to finite automaton forms the pumping lemma. Every state in a FA (finite automaton) consumes an input symbol and switches to another state. A state consumes or takes in more than one input if the state has a loop. On consuming an input, a state with loop transitions to itself and thus allowing itself to co nsume more input symbols. So without any looping states, if the length of the input string is m the number of states in the FA is n=m+1 . (the first state doesn’t consume any input , and is the extra 1) . Now what shall we conclude if the length of the accepted string is greater than the number of states by more than one. n>m+1 .  That is, the number of symbols in the input string is much greater the number of states. Well we can readily conclude that there is one or more states that consume more than one input, or one or more states have loops. The input symbols consumed by loops become a substring. The substring that is consumed by the looping states can repeat again and again and still be consumed by those looping states.

Those familiar with pumping lemma might say this this is just pigeon hole principle and the lemma has more things to it. But I think this is pretty much soul of the lemma and the additions are just for specificity and for things to work. So for being precise we say there is a string thats is accepted by a FA (thus belongs to a regular language) and is longer than the number of states . This string as its longer than the number of states has a substring that is accepted by a loop. Because these loops don’t restrict the number of such substrings the substrings can repeat. When theses substrings repeat they produce strings longer than the original. These new and longer strings are also accepted by the FA. Therefore these new strings should also belong to the regular language the FA represented. The repetition of the substring is the ‘pumping’ in the pumping lemma. Thus we can say if a language is regular its strings can be pumped. Therefore if we disprove the pump-ability of a language then the language is not regular. The lemma is not yet fully specific there are certain restrictions which shall follow.

Now in order to start proving that certain languages are non regular we need to enter a challenge mode. We need someone, an adversary who claims that a particular language is regular. The adversary surely must have built the FA for it (which is a lie) but doesn’t want to show it to us, lets guess he/she doesn’t believe in the principles of free software. Your adversary may not want to show the FA, but lets ask him/her the number of states in the FA. And lets say the reply is n. Now lets take a string, z, that belongs to the regular language under scrutiny and in length is greater than or equal to n. Surely there must be some looping states in the FA ( |z|\geq n doesn’t necessarily mean looping states, but the following conditions will make it right). Now we ask the adversary , since he/she knows the innards of his FA, to partition the string z such that he/she marks out the pump-able substring as z=u(v)^{i}w . Where v is the looping substring, and the super-script i means it can be pumped. With the condition that |uv|\leq n and |v|\geq 1 .

Now lets assume we have an adversary who claims that a language given as 0^{m}1^{m} | m>0 is regular. The example strings that belong to this language are 01,0011,0000011111  . The exchanges between you and the adversary is as follows.

  •  You ask the adversary how many states the FA has.
  •  Adversary replies with say 4 ( n=4 )
  •  You choose a string , z , that belongs to the language who’s length is a function of n.  The string you choose is 0^{4}1^{4} \Rightarrow 00001111 ( |z|\geq n )
  •  The adversary verifies that z indeed belongs to the language.
  •  You now ask the adversary to partition the string , marking out the repeating substring as z=u(v)^{i}w , because the length of the string you chose was greater than n. The condition being that |uv|\leq n and |v|\geq 1
  •  The adversary now partitions the string as he/she sees fit. (the adversary is clearly lying or doesn’t really know how to construct a FA). The partitioning the adversary proposes is {\xrightarrow[00]{u}}{\xrightarrow[00]{v}}{\xrightarrow[1111]{w}} .
  •  You verify if the conditions were met. Now you chooses a i=2 and pump in the substring v   twice. You get 00\overbrace{0000}1111 \Rightarrow 0000001111 , which clearly doesn’t belong to the language 0^{m}1^{m} . If the language was regular according to the pumping lemma the new substring must also belong to the language. Here that doesn’t happen.
  •  You declare the language has been proven non-regular and the adversary goes back home defeated.

The challenge method is the correct way to prove a language is non regular using the pumping lemma. But that really means you have to play double role, and act out the adversary by yourself.Now let me try to windup by answering the obvious questions that you should have asked. Why you chose z based on n, why the conditions are important and why you chose i=2 and pumped it only twice.

The conditions and the choice of z are to make sure the lemma works, otherwise the adversary can partition the string in ways that could be pumped. Lets look at these one by one.First lets consider the most obvious one, |v|\geq 1. Well if v was empty, |v|=0 , then v could be pumped any number of times and the string would be the same and surely be accepted again by the FA. Thus v should not be empty. To justify the other conditions we need another language. Well the other conditions aren’t really required for disproving that 0^{m}1^{m} is non regular. But for example another language given as ww | w\in\left \{ 0|1 \right \}^{*} can be proved to be regular if we don’t enforce those conditions.Possible strings in this language are 00, 0101, 1111,100001,.. etc. Assume we don’t enforce |uv|\leq n and the input we gave was z=001001 . The adversary can now partition the string as \xrightarrow[]{u}\xrightarrow[001001]{v}\xrightarrow[]{w} , with u=w=\epsilon (empty string), v=z . Now this could be pumped and still be in the language. Now on choosing the right string z. Assume we are dealing with same language and we chose z=01010101 . Now the adversary can partition the string as z=\xrightarrow[01]{u}\xrightarrow[0101]{v}\xrightarrow[01]{w} , where v=0101 , and pump v any number of times and still produce strings in the same language. So choosing the string in the first place in very important. The best way to choose z would be to incorporate n , the number of states, into the string. For example 0^{n}10^{n}1 is good enough for disproving this one. Now in disproving 0^{m}1^{m} , why did you choose  i=2 , well you can choose any value for i . If one value doesn’t help, choose another.

Before stopping let me also make it certain that the pumping lemma can only be used to prove a language is not regular. It can not be used to prove a language is regular. If a string cannot be pumped then language is non regular but if it can be pumped then its not necessary that language is regular. So thats it. What do you think? Did this help you understand the lemma, or did I just confuse you more, or did I give some false ideas, or do you think this was just overly explained and unwontedly stretched? Go ahead and comment about it.

 
 
PS.
-The examples were taken from MIT OCW Automata, Computability, and Complexity lecture notes, there’s more examples in there.  (kinda feel i should have just provided this link here instead of this write-up )
-This was the first time i used Latex, should have been easy but wordpress made it painful..really painful.
-and the first time i wrote a full prose in Vim.. VimRocks!!

To live is to fight , fight the demons outside and inside you. Agree ? Disagree?… Anyways this write-up is not about life nor about fighting your demons, so let me not go any further with that. Instead let me lead you to some rather trivial notions about the basic alphabet of the language of science. The language of science? Yes mathematics. I remember a line, from a famous Malayalam movie, uttered by a headmaster of a school (a character played to perfection by Thilakan) to instill fear and awe in the minds of his students – “without mathematics earth is nothing but a very big zero!”. If you are a Malayali, I guess you might remember this dialogue but its up to you the reader to decide whether that’s true or not! Lets return from cinema and focus on Numbers – the basic alphabet of math.

image not owned by the author. If objectionable please leave a comment to contact.

Here is the fun thing, why fight demons and focus on numbers on the same paragraph? To tell the truth numbers are one of the demons I fight inside me! (Ya laugh! :D) There is something in them that makes me loose cool! The reason for my unease with number is the fact that I usually don’t get them right. Even with basic arithmetic I make it stupid when they come in slightly larger proportion (how large? :D). My past experiences comes to haunt me when dealing with numbers, yes the bloody feedback! Or the cliché, “vicious cycle”, arghh! Even though I demonise numbers in my own ways I can tell you that numbers are something that we all take for granted. As a Computing Science aficionado I understand the importance of abstraction and how its a vital key to learning -”learn to use first, then ask the big question of how and why!”. But after you learn to use its probably good to ask a “how?” or a “why?”.

We are surrounded by numbers wherever we are and spew them out in all directions for every interaction we make with the physical world. Since these things are all around us we generally don’t try to understand them. If someone asks you what are numbers, what will your answer be? If someone asks me what are birds I ill probably point to a crow or sparrow and tell that’s a bird. So would your answer be like ‘hundred’ , ‘10’, ‘1010’ or ‘XV’ ? If you are telling ‘10’ is a number it would be like me pointing at a picture of a bird instead of pointing at a real bird on a tree or in the sky. We cant deal with numbers the same way as we deal with real-world or physical things, why? Because numbers are abstract things they don’t exist as tangible objects in the real world. Since they are abstract things they live solely in our minds, an idea. That’s what a number is , an idea or a concept that helps you keep count. Its the relations that we make with this idea that fills our world with numbers. ‘10’,’hundred’ are all representation of these relations. It would be wrong to say its we humans who came up with this idea, because all creatures have some sense for measuring and comparing quantities. Else a dog would try its chance with a rival pack of dogs the same way its would stand its ground when challenged by a single adversary. Surely a dog can measure resistance offered by a single dog over a pack of dogs, and thus when challenged by a pack it would immediately take flight or get submissive. So if you aren’t a creationist you should thank evolution for gifting you the notion of measurement. But probably we are the first creatures to represent that idea outside of our own brains. We humans have come up with systematic methods to represent this abstract thing, using symbols along with certain primitive operations. The first attempts at representing numbers would have been the unary-system that had n repetition of a symbol to represent n. So if the # was chosen then a single # would mean 1 and ##### would mean 5. The unary system was then probably enhanced by systems like the Roman numerals where certain repetitions of symbol would be replaced by another symbol. And then came the big breakthrough the positional-number system where the value represented by a group of symbols depended not just on the symbol themselves but by position they occupied in that group. The first of its kind is credited to a base-60 system by the Babylonians. The base-10 number system that we all use now to think about numbers came from India and it packaged an idea then unknown to the rest of the world, the idea of zero or nothingness. The West learns about this new system from the Arab traders and they happily name it ‘Arabic numerals’, pathetic!

I think I ill wrap it up here. But I guess I had a few more thoughts to share in this regard, but then this write-up had remained in draft form for than three months now. Also I don’t seem like able to recollect and reproduce other ideas I might have had, so I guess this deserved a much needed closure. Likewise I had mentioned in my previous write-up about a continuation article, I meddled with that idea for some time but didn’t land on anything concrete because the core itself was easily refutable. After that I went lost , down in some drain, not doing anything just big time lazy. At this moment I am trying best to bootstrap myself to bring back the days of activity and zest.

scale of infinite precision

I guess many of us at many a times  have acted illogically, and probably have made statements that are logically incompatible to each other. If at one point in time you say something ‘is’ and your consequent statements directly imply something ‘is not’, then your ‘is’ and ‘is not’ statements attack each other and  together form a contradiction. Contradictions can be quite interesting, so think about it; how often have you contradicted yourself? If your answer is ‘not much’ well good for you else others might call you a hypocrite. If you are someone who likes to take part in sporty debates with your friends or colleagues, once in a while you will find yourself making contradictory statements. Debates are helpful in making new ideas and to accelerate thought processes since you are pushing your brain to come up with new ideas to prove your point but sometimes you loose track of your previous idea and comes up with a new one that basically pulls your leg! Another related or equivalent term is `paradox`. A set of logical statements that concludes in a contradiction is a paradox. Paradoxes seems to defy logic and certain good ones will give a bang on your head and make you smile. Wikipedia just showed me that there are two kinds of paradoxes. Ones that are seemingly logical but are in fact absurd, called Falsidical paradoxes and ones that seem absurd but in real are logical, Veridical paradoxes.

In the reminder of this post I am gonna talk about a Falsidical paradox. And how the proof for the falsity of its logic made me arrive at an idea, which now becomes the title of this post.  In the next post I shall give you a very interesting Veridical paradox along with its philosophical impact.

Two friends of mine and me were walking the roads of our college campus at night talking this,that and technology. When suddenly one of them asked the other to tell me about a conversation they had the day before, about a paradox. The other, Sreekumar, said its puzzling but  flawed and that he already proved that by a piece of code. Probably you must have heard about proof by contradiction and alike but never ‘proof by code’? but sigh, that’s what programmers do. Nijil, the one who started this talk, quickly jumped in to defend that its not flawed and that its been puzzling people for ages. They then put aside their fight and finally settled to tell me about this strange thing.

Assume two guys X and Y decided to run a race but one, Y, starts 10 seconds ahead of the other. At some point in time Y crosses a checkpoint,p1, and some seconds later X also moves past it. By the time X crossed the checkpoint p1, Y has advanced some distance ahead of p1. Lets mark the distance advanced by Y as p2. By the time X manages to move past p2, Y has again moved a little more further. And thus by the virtue of the fact that X allowed an advantage to Y of starting early, X can never win the race however fast he runs because each time X crosses Y’s current position Y would have moved further, however small it be.

So, did you feel the bang, did you smile? This interesting paradox belongs to a set paradoxes called Zeno’s paradoxes, and is due to a Greek philosopher Zeno of Elea (a place in Italy). Told through the ages, this paradox replaces our X with Achilles (the great warrior of Homer’s Iliad, or remember Brad Pitt’s Troy(2004)? ) and our Y with a Tortoise (that wise Tortoise of Aesop which outwitted the hare in another race!). The clever Tortoise succeeds in convincing Achilles that he would fail, given the tortoise starts first, and Achilles accepts defeat before the race! Even though this paradox seems to prove by some mathematical reasoning that Achilles can never defeat the Tortoise in that race, from our real world experience we know it never happens that way. If someone gets a head start all you need to do is to run faster than you would if the race was fair. So how did Zeno manage to fool us? Hold on,let me continue from where I left off in the conversation with my friends. Feeling the bang I started to think, smiling. But before I came to something solid, Sreekumar jumped up and started describing his idea of what went wrong. The first few words that came from his mouth brought a flurry of thoughts into my mind, and there I was seconding Sreekumar even before he spoke a line! I am not sure if I am exaggerating this, but that’s what I remember of that night.  Before I get to what we shoveled down Nijil’s ears that night, let me give you a similar picture. Normal motion, I guess, is usually captured in 24 frames per second (fps) in a camera (i.e. the camera takes 24 photographs in one second and plays it to you one after the other). Once captured by the camera if you watch this video using the same frame rate you get to see the motion as you would see it live, i.e. 24 fps recording and 24 fps playback.  What happens when the frames per second is increased from 24 to say 240 for recording? Assuming that the playback fps is never changed (24 fps). Of course you get a slow motion video. The reason for this is, in one second the new camera setting caused the camera to produce 240 frames per every second instead of 24. And in playback 240 frames take much more time than 24 frames. A 10 times increase in playback time causes a slowdown of 10 times in the video. This new video though is much slower than the actual motion, is much more precise in its description of the motion. You get to see exactly how the motion happened. But then you might still be missing some detail. So we crank up the camera settings to a higher fps, resulting in much more precise motion. Increase the fps even more (tending to infinity?) and the resulting video would be so slow that there will be no perceivable motion, or the object that was in motion is now in rest, not moving at all. Even though in reality the object is moving the video shows us that the object is at absolute rest. So, did you find the similarity of how in reality Achilles would have easily won (well he is mighty warrior!) but Zeno showed us he could never win that race? Yes, this is exactly how Zeno fooled us.

Consider the Tortoise has lead of 1 feet at some point in the race. Every one  knows between two points infinite new points can be defined. Zeno roots his paradox in the fact that its impossible to cover infinite number of points in finite amount of time (yes, P!=NP). Well that’s true but here the infinite number of points is within the one feet of distance on the road, and all those infinite number of points could be covered by a single footstep! Achilles really don’t have to step on all these points separately. This is where the title of this post comes in. What if you have a ruler that shows you say 30 cm in total, along with markings for each millimeter, but this is no ordinary ruler. Look closer between two consecutive mm markings and the ruler expands the distance between those two markings giving you markings for a smaller unit, allowing you more precision. This expansion continues infinitely giving you infinite precision. Zeno considered the race track as a scale (ruler) of infinite precision that produces the same results as the camera with infinite fps. Just like our camera that showed that moving object was at absolute rest, Zeno when he measured the race track with the scale of infinite precision effectively froze Achilles on the track. How can Achilles win the race now? he is frozen on the track, paralyzed and helpless.

So now you have new tool in your tool-chest, other than pausing time what else can you do with this scale-of-infinite-precision? I don’t know, may be you could use its idea to prove or disprove some other twisted ideas. I myself have tried to use it in a discussion with a good friend of mine on philosophical grounds, not sure I was successful though. But I am certain of one thing you can never use it for the same purpose as you would use any ordinary ruler, to measure that is. Coming back to my friends at college, I wish I could include here Sreekumar’s code which will help convince Achilles that he will win the race but this post is already too long. And I am glad Nijil didn’t google on this paradox before telling about it that night!