Hints¶
NB. The rendering of the questions is better in the PDF lab exercises file.
Minimum pumping length¶
The PL says that every RL has an associated pumping length \(p\), such that every string in the language can be pumped as long as it has at least \(p\) symbols.
Note that if \(p\) is a pumping length for a language then so is any other length \(\geq p\). We define the minimum pumping length to be the smallest such \(p\).
Example
For example, if \(L=\texttt{ab}^*=\{\texttt{a}, \texttt{a}\texttt{b}, \texttt{a}\texttt{b}\texttt{b},\ldots\}\) then its minimum pumping length is 2. This is because the string \(w=\texttt{a}\texttt{b}\) can be pumped by starring the \(\texttt{b}\): \(\texttt{a}\texttt{b}^*\); while the shorter string \(w=\texttt{a}\) cannot be pumped.
Q1  Minimum pumping length
For each of the following languages, give the minimum pumping length and justify your answer.
 \(\texttt{aab}^*\)
 \(\texttt{a}^*\texttt{b}^*\)
 \(\texttt{aab} + \texttt{a}^*\texttt{b}^*\)
 \(\texttt{a}^*\texttt{b}^+\texttt{a}^+\texttt{b}^* + \texttt{ba}^*\)
 \((\texttt{01})^*\)
 \({\varepsilon}\)
 \(\texttt{b}^*\texttt{a}\texttt{b}^*\texttt{a}\texttt{b}^*\)
 \(\tt 10(11^*0)^*0\)
 \(\tt 1011\)
 \(\Sigma^*\)
Notation: superscript plus
The notation \(\texttt{a}^+\) is equivalent to \(\texttt{aa}^*\), i.e. 1 or more \(\texttt{a}\)'s (as opposed to \(\texttt{a}^*\) which means zero or more \(\texttt{a}\)'s).
You can design minimal NFAs for the languages and then use the type of discussion shown in the lecture, but it is safer to list the first few strings in the language, in increasing length, and then check to see at what length you can find a substring that you can pump from an accepted string.

\(\texttt{aab}^*=\tt \{aa,aab,aab^2,aab^3,aab^4,aab^5,aab^6,\ldots\}\), sorted in ascending order with respect to string length.
Consider \(\texttt{a}\texttt{a}\) and \(\texttt{a}\texttt{a}\texttt{b}\) (the first two shortest strings in the language).

\(\tt \texttt{a}^*\texttt{b}^* = \{{\varepsilon},a,b,a^2,b^2,ab,a^3,b^3,aab,abb,a^4,b^4,\ldots\}\)
\({\varepsilon}\) is never pumpable. Check the next ones.

\(\texttt{aab} + \texttt{a}^*\texttt{b}^* = \tt \{aab\} \cup \{{\varepsilon},a,b,a^2,b^2,ab,a^3,b^3,aab,abb,a^4,b^4,\ldots\}\) which is just \(\tt\{{\varepsilon},a,b,a^2,b^2,ab,a^3,b^3,aab,abb,a^4,b^4,\ldots\}=\texttt{a}^*\texttt{b}^*\) again, so ...

\(\texttt{a}^*\texttt{b}^+\texttt{a}^+\texttt{b}^* + \texttt{ba}^*=\tt \{ba,aba,bab,bba,aab,\}\cup \{b,ba,ba^2,ba^3,\ldots\}\)
This is a union of two languages:

The RegEx \(\texttt{a}^*\texttt{b}^+\texttt{a}^+\texttt{b}^*\) gives \(p=\_\_\_\) as we can loop _ from its shortest string ______.

The RegEx \(\tt ba^*\) also gives \(p=\_\_\_\) as we can loop _ from its _ shortest string ___.
So, we conclude that the given language has \(p=\_\_\_\) (the shortest of the two lengths, which happen to be the same in this example).


\((\texttt{01})^*=\tt \{{\varepsilon},01,0101,010101,(01)^4,(01)^5,\ldots \}\)
So starting from \(\tt 01\) we can set \(x=z=\_\_\_\) and \(y=\_\_\_\) in the Pumping Lemma. Hence, \(p=\_\_\_\).

\({\varepsilon}\)
This RegEx represents the language that only contains the empty string: \(\{{\varepsilon}\}\).
There is no way of writing \({\varepsilon}=xyz\) with \(y\neq \_\_\_\), so it suffices to let \(p=\_\_\_\).
The language is finite (and therefore regular), and there are no pumpable strings!
Tip
The empty string \({\varepsilon}\) is the only possible string of length zero over any alphabet, and it is not pumpable in any language, so \(p\) is always \(\geq 1\), unless the language is the empty language \(\emptyset\).**

\(\texttt{b}^*\texttt{a}\texttt{b}^*\texttt{a}\texttt{b}^* = \tt \{aa, baa, aba, aab,b^2aa,ab^2a,aab^2, baba, baab, abab,\ldots \}\)
Here, the shortest string \(\tt b^0 ab^0 ab^0 = aa\) is not pumpable (because ......................).
However, all the strings of length _ are _ producing e.g. \(\tt b^*aa\) from \(\tt baa\). So \(p=\_\_\_\).

\(\tt 10(11^*0)^*0 = \tt \{ 100, 10100, 101100, 1011100, 1010100, \ldots\}\)
The shortest string \(\tt 100=10(11^*0)^{\_\_\_} 0\) is __, but the next one \(\tt 10100=10(11^00)^{\_\_\_} 0\) is ____, producing \(\tt 10(10)^* 0\), so \(p=\_\_\_\).

\(\tt 1011\)
This RegEx represents the language that only contains one string: \(\tt\{1011\}\).
If we pump any symbol then the length of the resulting string will be at least 5, so it cannot be a member of this language.
Hence, it suffices to let \(p=\_\_\_\).
The language is finite (and therefore regular), and there are no pumpable strings!

\(\Sigma^*=\{{\varepsilon},\ldots \}\) is the language of all possible strings over the alphabet \(\Sigma\).
In particular, if \(\texttt{a}\) is a symbol then \(\texttt{a}^*\) is also in \(\Sigma^*\), so \(p=\_\_\_\).
PL applied to RLs¶
When we try to apply the Pumping Lemma to a Regular Language the Prover wins, and the Falsifier loses.
Q2
Show why Falsifier loses when \(L\) is one of the following RLs:
 \((\texttt{a}\texttt{a})^*\)
 \((\texttt{aa} + \texttt{bb})^*\)
 \(\texttt{0}\texttt{1}^*\texttt{0}^*\texttt{1}\)
 \(\{\texttt{00}, \texttt{11}\}\)
 \(\emptyset\)
For each language, find a suitable value for \(p\) and use it in the PL Game.

\((\texttt{a}\texttt{a})^*=\{\varepsilon, \texttt{aa}, \texttt{aaaa}, \ldots\}\)
\(p=\_\_\_\) etc.

\(\{\texttt{00},\texttt{11}\}\)
This is a finite language, so Prover chooses \(p=\_\_\_\).
Falsifier cannot choose a string that is long enough. (\(w\geq 3\) but the two available strings are only 2 symbols long.) So Falsifier loses!

\((\texttt{aa} + \texttt{bb})^*=\{\varepsilon, \texttt{aa}, \texttt{bb}, \texttt{aabb}, \texttt{bbaa}, \ldots\}\)
Prover chooses \(p=\_\_\_\) and \(y=\\_\_\_\) or \(\_\_\_\), depending on the string chosen by the Falsifier .

\(\texttt{0}\texttt{1}^*\texttt{0}^*\texttt{1}\)
Prover chooses \(p=\_\_\_\) and \(y=\texttt{0}\) or \(\texttt{1}\), depending on the string chosen by the Falsifier .

\(\emptyset\)
Falsifier has no strings to choose from! Prover may set \(p=0\) or any other value.
PL Game¶
The following are almost complete proofs that some languages are not regular, using the Pumping Lemma (PL). Complete them by filling in the hidden details. (Some were done in the lecture using less formal notation.)
Q3¶
\(L=\{\texttt{0}^n\texttt{1}^n\mid n\geq 0\}\)
Show that the language \(L=\{\texttt{0}^n\texttt{1}^n\mid n\geq 0\}\) is not regular.
Prover claims \(L\) is regular and fixes the value of the pumping length \(p\).
Falsifier challenges Prover and picks \(w=\texttt{0}^p\text{___}\in L\) and verifies it has the required length: \(w=\text{___}\geq p\).
Prover tries to decompose \(w\) into three parts \(w=\text{___}\) but sees that the condition \(xy\leq \text{___}\) forces \(y\) to only contain the symbol \(\text{___}\).
Furthermore, \(y\) cannot just be the empty string because of the condition ______.
So it is forced to choose \(y=\texttt{0}^d\) for some \(d\geq 1\).
Falsifier now sees that
and hence \(xy^2z\) does not belong to \(L\). This is because \(d\geq 1\implies p+d>p\), and hence \(xy^2z\) has more 's than there are 's. (They need to be equal for it to be in the language.)
Note
Note that we could use any of \(xy^3z, xy^4z, \ldots\).
In fact, we could have even used \(xy^0z=xz\); we end up with less \(\texttt{0}\)'s than there are \(\texttt{1}\)'s.
It's from the lecture. (Minute: 7.)
Q4¶
\(L=\{ww\mid w\in\{\texttt{0},\texttt{1}\}^*\}\)
\(L=\{ww\mid w\in\{\texttt{0},\texttt{1}\}^*\}\).
Prover claims \(L\) is regular and fixes the value of the pumping length \(p\).
Falsifier challenges Prover and chooses \(w=(\texttt{0}^p\texttt{1})(\texttt{0}^p\texttt{1})\in L\).
This has length
Prover The PL now guarantees that \(w\) can be split into three substrings \(w=xyz\) satisfying \(xy\leq p\) and \(y\neq {\varepsilon}\).
Falsifier Since
with \(xy\leq p\) then we must have that \(y\) only contains the symbol .
We can then pump \(y\) and produce \(xy^2z=xyyz\not\in L\) because the first half the second half.
So \(L\) is not regular.
It's from the lecture. (Start: 13:38)
Q5¶
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid 0\leq i<j<k\}\)
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid 0\leq i<j<k\}\)
Prover claims \(L\) is regular and fixes the value of the pumping length \(p\).
Falsifier challenges Prover and chooses
Here \(w=p+\text{____________} \;\text{______}\; p\)
Prover writes
where \(xy\) is a string of 's only
Falsifier forms
because \(y\geq 1\).
This is more or less similar to Q4.
Q6¶
\(L=\{\texttt{a}^i \texttt{b}^j \mid i>j\}\)
\(L=\{\texttt{a}^i \texttt{b}^j \mid i>j\}\)
Prover claims \(L\) is regular and fixes the value of the pumping length \(p\).
Falsifier challenges Prover and chooses
Here \(w=\text{__________} \;=2p+1\text{____}\; p\)
Prover writes
i.e. \(xy\) is a string of 's only
Falsifier forms
because \(y\geq 1\). (so \(p+1\text{_________}\leq p\)).
It's from the lecture. (Start: 18:16)
You need to "pump down".
Q7¶
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid i>j>k\geq 0\}\)
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid i>j>k\geq 0\}\)
Prover claims \(L\) is regular and fixes the value of the pumping length \(p\).
Falsifier challenges Prover and chooses
Here \(w=\text{_______}+(p+1)+0 \;\text{______}\; \text{____}.\)
Prover writes
where \(xy\) can have a maximum of symbols, so \(xy\) must be a string of 's only
Falsifier forms
because \(y\geq 1\).
This is similar to Q6.
JFLAP (Optional)¶
PL Game with JFLAP
Go through the JFLAP tutorial and then try all the "games."
JFLAP plays the role of Falsifier and you play the role of Prover .
Assume \(\Sigma=\{\texttt{a},\texttt{b}\}\) unless otherwise specified.
Note
Note that some of the languages below are actually regular  in this case, you will need to devise a strategy for Prover to always win no matter what Falsifier chooses as a challenge string.
The list of languages is as follows:

\(\{ \texttt{a}^n \texttt{b}^n\mid n\geq 0\}\)

\(\{ w\in\Sigma^*\mid n_\texttt{a}(w)<n_\texttt{b}(w)\}\) i.e. language of strings which have less \(\texttt{a}\)'s than there are \(\texttt{b}\)'s.
 \(\{ ww^R\mid w\in\Sigma^*\}\)
 \(\{ (\texttt{a}\texttt{b})^n\texttt{a}^m \mid n>m\geq 0\}\)
 \(\{ \texttt{a}^n \texttt{b}^m \texttt{c}^{n+m}\mid n\geq 0, m\geq 0\}\)
 \(\{ \texttt{a}^n\texttt{b}^\ell \texttt{a}^k\mid n>5, \ell>3, \ell\geq k\}\)
 \(\{ \texttt{a}^n\mid n \text{ is even}\}\)
 \(\{ \texttt{a}^n \texttt{b}^m\mid \text{$n$ is odd or $m$ is even}\}\)
 \(\{ \texttt{b}\texttt{b}\texttt{a}(\texttt{b}\texttt{a})^n\texttt{a}^{n1}\mid n\geq 1\}\)
 \(\{ \texttt{b}^5 w\mid w\in\Sigma^* \text{ \textbf{and} } 2 n_\texttt{a}(w)=3n_\texttt{b}(w)\}\)
 \(\{ \texttt{b}^5 w\mid w\in\Sigma^* \text{ \textbf{and} } n_\texttt{a}(w)+n_\texttt{b}(w)\equiv 0\pmod 3\}\)
 \(\{ \texttt{b}^m(\texttt{a}\texttt{b})^n(\texttt{b}\texttt{a})^n\mid m\geq 4 , n\geq 1\}\)
 \(\{ (\texttt{a}\texttt{b})^{2n}\mid n\geq 1\}\)
 \(m\) is used instead of \(p\) (the pumping length).
 \(i\) is used instead of \(k\) in \(xy^k z\).

\(n_\texttt{a}(w)\): the number of occurrence of the symbol \(\texttt{a}\) in the string \(w\).
e.g. \(n_\texttt{a}(\texttt{aba})=2\) and \(n_\texttt{b}(\texttt{aba})=1\).

\(w^R\): the reverse string of \(w\), e.g. \(\texttt{a}\texttt{b}\texttt{b}^R=\texttt{b}\texttt{b}\texttt{a}\).

\(\texttt{a}^p\texttt{b}^p\)

\(\texttt{a}^p\texttt{b}^{p+1}\)

\(\texttt{a}^p\texttt{b}^{2p}\texttt{a}^p\)

\((\texttt{a}\texttt{b})^{p+1}\texttt{a}^p\)

....

....

Regular

Regular

....

....

....

....

Regular
Warning
The games played by JFLAP are for a specific challenge string. This is only meant to give you a feel for how the general game proceeds. When we write our proofs we are not allowed to choose a fixed value for \(p\).
Orange¶
Q1¶
ADD
Let \(\Sigma=\{\texttt{0},\texttt{1},\texttt{+},\texttt{=}\}\), and
ADD
be the language given by
Show that ADD
is not regular.
Prover claims is regular and fixes the value of the pumping length .
Falsifier challenges Prover and chooses to be
Prover can only have 1
's in , so for some
Falsifier constructs and finds it to be
which is not correct.
Q2¶
Powers of 2
Let \(L=\{1^{2^n} \mid n\geq 0\}\). Show that \(L\) cannot be regular.
➊ Prover claims L is regular and fixes the value of the pumping length p.
➋ Falsifier challenges Prover and w = 12p
➌ Prover writes
a b 2p−a−b
x = 1 ,y = 1 ,z = 1
where 1 ≤ b ≤ p.
➍ Falsifier
xyyz = 12p+b The next string after 1p2 in terms of length is 12p+1 = 12p+2p but
2p < 2p + b < 2p + 2p. because 1 ≤ b ≤ p < 2p So xyyz∉L.
Q3¶
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid j\neq i\text{ or } j\neq k\}\)
\(L=\{\texttt{a}^i \texttt{b}^j \texttt{c}^k\mid j\neq i\text{ or } j\neq k\}\)
➊ Prover claims L is regular and fixes the value of the pumping length p.
➋ Falsifier challenges Prover and chooses

p!+#pp!+#p#
w = apb c
Here w = p + 2(p! + p) ≥ p.
➌ Prover writes
 
p!#+#p p!+#p#
w = (xy)z = (ap)b c
where xy is a string of a’s only
➍ Falsifier forms
p!+pp!+p
xykz = ap+ (k−1)yb c
where k = 1 + p! ∕y. This gives ap!+pbp! + p c p! +p which is not in the language.