{"id":1418,"date":"2011-05-01T15:38:58","date_gmt":"2011-05-01T19:38:58","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1418"},"modified":"2011-05-01T15:38:58","modified_gmt":"2011-05-01T19:38:58","slug":"what-if-its-not-regular-pump-it","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/05\/01\/what-if-its-not-regular-pump-it\/","title":{"rendered":"What if it's not Regular? Pump it!"},"content":{"rendered":"

At this point, we’ve seen a fair bit about regular languages, and we’ve gone through the introduction to context free languages. We know one way of showing that a language is regular or context free: if you can write a (regular\/context free) grammar for a language, then that language is necessarily (regular\/context free). But… what if we have a language that we suspect is not<\/em> regular? <\/p>\n

<\/p>\n

Suppose, for example, that we have a context free grammar for a language. The fact that we specified it using a context free grammar doesn’t mean that the language requires<\/em> a context-free grammar. Sometimes it’s easier to write things with a CFG, even if it’s possible to write them with a regular grammar. We suspect that it really can’t be done using a regular grammar – but we’re not sure. Just because we think<\/em> that we can’t write a regular grammar for the language doesn’t mean anything. It’s possible that we’re wrong – that there’s some way of writing an alternative grammar that’s regular. So.. how can we actually show that a language isn’t regular? (Or stepping up a level, that a language isn’t context free?)<\/p>\n

There’s a clever tool called the pumping lemma<\/em>, which we can use to show that a language isn’t regular. (And there’s a variation of it that can be used to show that a language isn’t context free.) What it does is exploit a simple property of a regular language in a way that allows us to use it to show that a language isn’t regular.<\/p>\n

One of the fundamental limits of a regular language is that it can’t have deep patterns. It’s built one terminal symbol at a time, from left to right, without being able to look back at context. That’s essentially the process that we’re going to exploit. What the pumping lemma says is: given a language L, if we take any string in L above a grammar-specific minimum length, then that string will consist of three parts – a prefix (a), a center (b), and a suffix (c). If the string abc is in L, then any string that repeats<\/em> the center part any number of times will also<\/em> be part of L. So we can pump<\/em> the language: abc will be in L; abbc will be in the language; abbbc will be in the language, and so on. If we can find any string in L where there’s no pumpable center, then L isn’t regular.<\/p>\n

Let’s make it more formal, so that we can be precise. We need one quick notational thing – we’ll write the length of string s as |s|. With that, the pumping lemma says:<\/p>\n

If L is a regular language, then there exists an integer p ge 1 that depends solely on the structure of L, such that for every string s in L, if |s| ge p, s can be described in terms of substrings a, b, and c such that:<\/p>\n

    \n
  1. s = abc<\/li>\n
  2. |ab| le p<\/li>\n
  3. |b| ge 1<\/li>\n
  4. forall i ge 0, a(b^i)c in L<\/li>\n<\/ol>\n

    Now, how do we use this? Let’s look at how it works on the canonical example of a non-regular language: x^nb^y – a string which has a string of xs, followed by the same number of ys.<\/p>\n

    Let’s assume that this language is regular. We know that there must be some integer n, and that for anything longer than n, some part of any string longer than n must be pumpable.<\/p>\n

    So, let’s take the string x^{n+1}y^{n+1}. By the pumping lemma, we know that sum of the lengths of the prefix and the middle of the string have to be less than or equal to n. So the prefix, a, is any sequence of xs; we’ll say it’s length is m where m ge 0; and the middle, b has to be a sequence of at least one x – it’s n - m xs, and n - m ge 1. That is, we’ve broken the string into x^mx^{n-m}xy&{n+1}.<\/p>\n

    So if the language is regular, then we must be able to say that ab^ic is in the language. So x^mx^{n-m}^2xy^{n+1} must be in the language. If we simplify that, x{2n-m+1}y^{n+1} must be in the language. But xs than ys. That means that the language can’t be regular, because pumping it produced a string that’s not in the language.<\/p>\n

    One thing to be aware of – a mistake I made far too often in my first class that covered this – is that the fact that a language is pumpable does not<\/em> mean that the language is<\/em> regular. All regular languages are pumpable, but not all pumpable languages are regular. If you can’t pump a language, you’ve proved it’s not regular. But the fact that you can pump it doesn’t tell you anything. If you want to prove that a language is<\/em> regular, you have to either show a regular grammar, a regular expression, or a FSA that describes the language.<\/p>\n

    The regular language pumping lemma that I showed above is really easy to use. It takes a bit of practice to get comfortable choosing the basic structure of a string to pump – but the proofs are pretty much always as short as the one above. For context free languages, the basic concept is similar: you exploit the structure of the class of languages to find a structure that can be repeated – and then you show that your language of interest doesn’t contain that sort of repetitive structure. But since CFLs are a lot more expressive, and can describe more complex structures, the repetitive structure that you exploit is, similarly, more complicated.<\/p>\n

    The context free pumping lemma says:<\/p>\n

    If L is a context-free language, then there exists some integer p ge 1 suth that for any string s in L, |s| ge p, s can be divided into substrings u, v, x, y, z such that:<\/p>\n

      \n
    1. s = uvxyz<\/li>\n
    2. |vxy| le p<\/li>\n
    3. vy ge 1<\/li>\n
    4. uv^nxy^nz in L<\/li>\n<\/ol>\n

      So… Instead of just having a prefix, a middle, and a suffix, we’ve now got five subtrings. There are two<\/em> repeated parts, instead of just one, and there can be something in between them. And we’re pumping repetitions of both the front and the back. So if uvxyz in L, then uvvxyyz in L, and uvvvxyyyz in L, and so on.<\/p>\n

      It is more complicated than the regular language pumping lemma, but it’s still not awful. And proofs in it end up looking very much like the proofs with the regular language pumping lemma. For example, we could look at the language 1^n2^n3^n, which is a canonical example of a non-context-free language. The proof of that ends up being nearly exactly the same as the proof for x^ny^n for the context free languages. We set up the string so that both v and y must be 2s. Then we pump it, and show that we end up with more 2s than 3s. <\/p>\n","protected":false},"excerpt":{"rendered":"

      At this point, we’ve seen a fair bit about regular languages, and we’ve gone through the introduction to context free languages. We know one way of showing that a language is regular or context free: if you can write a (regular\/context free) grammar for a language, then that language is necessarily (regular\/context free). But… what […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[79],"tags":[107,132,217],"class_list":["post-1418","post","type-post","status-publish","format-standard","hentry","category-computation","tag-automata","tag-computation-2","tag-pumping-lemma"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-mS","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1418","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=1418"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1418\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1418"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1418"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1418"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}