pumping lemma for regular languages

to understand the power of finite automata, we must also understand their limitations. the puming lemma is used to prove that certain languages cannot be recognized by any finite automaton.
let's take the language $\text{[math]}$ . if we attempt to find a dfa that recognizes $\text{[math]}$ , we discover that the machine seems to need to remember how many 0s have been seen so far as it reads the input. because the number of 0s isn't limited, the machine will have to keep track of an unlimited number of possibilities. but it cannot do so with any finite number of states.
a technique for proving nonregularity stems from a theorem about regular languages, traditionally called the pumping lemma. this theorem states that all regular languages have a special property. if we can show that a language does not have this property, we are guaranteed that it is not regular. the property states that all strings in the language can be "pumped" if they are at least as long as a certain special value, called the pumping length. that means each such string contains a section that can be repeated any number of times with the resulting string remaining in the language.

if $\text{[math]}$ is a regular language, then there is a number $\text{[math]}$ (the pumping length) where if $\text{[math]}$ is any string in $\text{[math]}$ of length at least $\text{[math]}$ , then $\text{[math]}$ may be divided into three pieces, $\text{[math]}$ , satisfying the following conditions:

for each $\text{[math]}$ , $\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ .

where $\text{[math]}$ represents the length of string $\text{[math]}$ , $\text{[math]}$ means that $\text{[math]}$ copies of $\text{[math]}$ are concatenated together, and $\text{[math]}$ equals $\text{[math]}$ .
[cite:@sipser_comp_2012 theorem 1.70]

when $\text{[math]}$ is divided into $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ may be $\text{[math]}$ , but condition 2 says that $\text{[math]}$ . observe that without condition 2 the theorem would be trivially true.
condition 3 states that the pieces $\text{[math]}$ and $\text{[math]}$ together have length at most $\text{[math]}$ . it is an extra technical condition that we occasionally find useful when proving certain languages to be nonregular.

let $\text{[math]}$ be the language $\text{[math]}$ . we use the pumping lemma to prove that $\text{[math]}$ is not regular. the proof is by contradiction. assume to the contrary that $\text{[math]}$ is regular. let $\text{[math]}$ be the pumping length given by the pumping lemma. choose $\text{[math]}$ to be the string $\text{[math]}$ . because $\text{[math]}$ is a member of $\text{[math]}$ and $\text{[math]}$ has length more than $\text{[math]}$ , the pumping lemma guarantees that $\text{[math]}$ can be split into three pieces, $\text{[math]}$ , where for any $\text{[math]}$ the string $\text{[math]}$ is in $\text{[math]}$ . we consider three cases to show that this result is impossible.

the string $\text{[math]}$ consists only of 0s. in this case, the string $\text{[math]}$ has more 0s than 1s and so is not a member of $\text{[math]}$ , violating condition 1 of the pumping lemma. this case is a contradiction.
the string $\text{[math]}$ consists only of 1s. this case also gives a contradiction.
the string $\text{[math]}$ consists of both 0s and 1s. in this case, the string $\text{[math]}$ may have the same number of 0s and 1s, but they will be out of order with some 1s before 0s. hence it is not a member of B, which is a contradiction.

thus a contradiction is unavoidable if we make the assumption that $\text{[math]}$ is regular, so $\text{[math]}$ is not regular. note that we can simplify this argument by applying condition 3 of the pumping lemma to eliminate cases 2 and 3.
in this example, finding the string $\text{[math]}$ was easy because any string in $\text{[math]}$ of length $\text{[math]}$ or more would work. but often it isnt this trivial.
[cite:@sipser_comp_2012 example 1.73]

let $\text{[math]}$ . we use the pumping lemma to prove that $\text{[math]}$ is not regular. the proof is by contradiction.
assume to the contrary that $\text{[math]}$ is regular. let $\text{[math]}$ be the pumping length given by the pumping lemma. consider the string $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ must consist only of 0s, so $\text{[math]}$ . therefore, $\text{[math]}$ cannot be pumped. that gives us the desired contradiction.
[cite:@sipser_comp_2012 example 1.74]

[cite:@sipser_comp_2012 example 1.75]

[cite:@sipser_comp_2012 chapter 1.4 nonregular languages]

given $\text{[math]}$ defined by
$\text{[math]}$ prove that $\text{[math]}$ isnt regular.

assume in contradiction that $\text{[math]}$ is regular, let $\text{[math]}$ be the pumping length provided by the pumping lemma, for every string $\text{[math]}$ , since $\text{[math]}$ , $\text{[math]}$ has to be all $\text{[math]}$ 's but if we consider the result $\text{[math]}$ we see that pumping isnt possible, which gives us the necessary contradiction and so the language isnt regular.

prove that $\text{[math]}$ is nonregular.

i was challenging my understanding when i wrote this solution, trying to get a better grasp of the method.

it seems that by picking a string like $\text{[math]}$ we can pump it however we want with 0's and it would still be in the language because it wouldnt break the rule $\text{[math]}$ . but that isnt true, atleast not for all possible values of $\text{[math]}$ , if we pick all the exponents to be equal i.e. $\text{[math]}$ , and pick $\text{[math]}$ to be their length, i.e. $\text{[math]}$ , we would be restricting the "pumping string" $\text{[math]}$ to only 0's (like in [[blk:exa-pumping-lemma-2]]), and breaking the restriction $\text{[math]}$ first so that when we try to pump the string with 0's we would break the second restriction, $\text{[math]}$ , hence showing that the pumping lemma isnt satisfied by contradiction, and so the language is nonregular.

prove that $\text{[math]}$ is nonregular.

as usual, a proof by contradiction, assume $\text{[math]}$ is regular so that the pumping lemma holds, let $\text{[math]}$ be the pumping length provided by the pumping lemma, consider the string of length $\text{[math]}$ , this string cannot be pumped, because any string of length $\text{[math]}$ where $\text{[math]}$ isnt in $\text{[math]}$ because the next longest string after that of length $\text{[math]}$ is gonna be of length $\text{[math]}$ , and $\text{[math]}$ is smaller than $\text{[math]}$ for $\text{[math]}$ . so $\text{[math]}$ must be nonregular because assuming it is causes a contradiction.

given the language $\text{[math]}$
$\text{[math]}$ does it pertain the pumping lemma? is it regular?

is $\text{[math]}$ regular?
$\text{[math]}$

given $\text{[math]}$ where $\text{[math]}$ is regular but $\text{[math]}$ isnt. prove that $\text{[math]}$ isnt regular.

given
$\text{[math]}$

given $\text{[math]}$ :
$\text{[math]}$ $\text{[math]}$ pertains the pumping lemma for regular languages. try to find $\text{[math]}$ equivalence classes.