5
I was reading by HOPCROFT and had difficulty applying the pumping lemma in a formal way to exercises to prove that a language is not regular.
In this case, I refer to the Pumping Motto for regular languages.
In some cases I was able to show specific cases, but my teacher only accepts general evidence in the evaluation.
3
The motto of pumping is a condition sine qua non of regular/context-free languages (depending on which one you are using, of course). However, it is not a condition sufficient.
As you asked to focus only on the pumping lemma for regular languages, this note here says that there is the pumping lemma for context-free languages.
This means that for every regular language, it is possible to "pump more often" a string. I give more examples of this in this answer.
What is the thinking behind the pumping lemma? Well, that we have a running Markov process (this process is, as implied by Chomsky in your article, the finite regular language automaton) that generates/identifies words in a regular language. So this means that there is a route between the beginning of the word and its end. If, by chance, this route makes a loop, I could repeat it endlessly and still be something valid in the Markov process. So, since this is a Markov process, I can repeat the loop that the new word generated by this new route will be in the regular language.
The article by Chomsky is a very good and fun reading, after all, "colorless green ideas sleep furiously". Only it looks like it was scanned and the PDF source didn’t get very nice to read. Better read printed.
Read also that answer, has even a square of curiosity to try to help not get lost between Chomsky’s terms and the terms of computer scientists/mathematicians. Imagine, Chomsky uses a term that exists for mathematicians, but with a totally different meaning...
Okay, is there an example of this Markov tie and process? Let’s take this finite automaton:
Let’s suppose I followed the following path (or suppose I recognized the word bbba):
q0 -> qb1 -> qb2 -> qb2 -> qa
Note that the edge qb2 -> qb2 forms a subroute that is a loop on qb2. The simplest possible loop, but it is a loop: starts at a vertex and stops on itself. In this loop, we produce exactly the third b of the word bbba. This means that we can go through this loop as many times as the new word will belong to the same language. That is to say, bbbbbba is also a valid word.
In the pumping lemma, this loop is indicated by the subpalavra y. What happens before y are the steps to get to the loop, which is the subpalavra x. What comes next is the long tail, which serves basically to end in an accepting state, the subpalavra w. Soon, to use the pumping motto you need a word x.y.z so that you can pump y as many times as you want.
It has a mathematical balcony (like
|x.y| <= pfor aplanguage dependent arbitrary and|y| >= 1) to ensure that the pumping is valid, but I will not go into more detail about it, I wanted to let a more formal idea about why the pumping motto works.I worked the motto of pumping more strongly in this answer
The pumping lemma is, as said before, a sine qua non condition of regular languages. That is, if the language does not satisfy the motto, then it is certainly not regular. Therefore, this lemma should be used to exclude languages from being classified as regular. It should not be used to classify positively how to regulate.
Basically, you need to choose a word that belongs to the language in question and divide it into x.y.z. Like you don’t know who you are p, then arbitrarily choose a word that somehow has this feature already embedded in it. For example, to prove that the language over a binary alphabet in which both letters appear in the same number of times, I chose the word "0"^p . "1"^p. That is, no matter what the value of p, he is contemplated. I won’t repeat my detailed test, but any y that you do will contain only 0s, then pump more often y will generate a word with more 0s than 1s, so the pumped word does not belong to the language. Therefore, it is not regular.
Annex:
Build a regular grammar that recognizes it. This is the direct proof. The pumping motto comes to say that no matter how hard you try, it will be impossible to create a grammar that you recognize exactly the desired language.
Browser other questions tagged computer-theory automata formal-languages
You are not signed in. Login or sign up in order to post.
That’s a great question, but I’m a little out of my mind to answer. I gave examples in other questions of the tag [tag:formal languages], must have a knowledge spread around. One of these examples was recent, is in this answer. In the case, returned to regular languages. But must have somewhere a motto of pumping for LLC in some loose response. I don’t know pumping lemma for context-sensitive languages, I also don’t think there is for unrestricted grammars (just remember, unrestricted grammars are Turing-complete)
– Jefferson Quesado