Pumping my ass

Cards (7)

  • To prove is regular: use any of the things a regular language is known to have/do
  • There is a length in any language, for which in words that are longer than it, it is possible to find a 3 way split of it such that the first 2 parts are not longer that the special length, the middle part specifically is not empty, and no matter how many times (inc. 0) you repeat the middle part the resulting word is still in the language
  • K = the number of states an automaton would have + 1
  • In a regular language, with an automaton that has 1+ loops, the u is the part leading up to the loop, v = the loop part, w = the rest of the run
  • Contraposition: if for all possible values of k, you can find a word with a length more than k, that no matter how uvw is legally broken up, you can find a number of repetitions of v that make the word illegal, it is not regular
  • Prove irregular: pick a word that is definitely in the language, and has more than k length, and show how changing the length of v would principally make the word illegal ie: (v has to be the start a, as otherwise |uv| would be too long, or first a repetition be <k, which is not the chosen word and also coincidentally illegal.)
  • To prove irregular, just have to find ONE word that is longer than k that cannot be broken up and looped