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

QHintMore hintsVideo

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 pump-able strings!

Tip

The empty string ${\varepsilon}$ is the only possible string of length zero over any alphabet, and it is not pump-able 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 pump-able (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 pump-able 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

QHintMore hintsVideo

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\}$

GameHint

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

\[xy^2z = xy\text{_____}z = 0^p\text{______}1^p = 0^{p+d} 1^p.\]

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}\}^*\}$

GameHint

$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

\[|w|=(p+1)+(\text{______})=\text{_______}\geq p.\]

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

\[w=(\texttt{0}^p\texttt{1})(\text{________})=xyz\]

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\}$

GameHint

$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

\[w=\texttt{a}^{\text{____}} \texttt{b}^{\text{____}+1} \texttt{c}^{\text{_____}+2}.\]

Here $|w|=p+\text{____________} \;\text{______}\; p$

Prover writes

\[w=(xy)z=(\texttt{a}^p) \texttt{b}^{p+1} \texttt{c}^{p+2}\]

where $xy$ is a string of 's only

Falsifier forms

\[xy^2z=\texttt{a}^{p+\text{_____}} \texttt{b}^{p+1} \texttt{c}^{p+2}\not\in L\]

because $|y|\geq 1$.

This is more or less similar to Q4.

Q6¶

$L=\{\texttt{a}^i \texttt{b}^j \mid i>j\}$

GameHint

$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

\[w=\texttt{a}^{\text{_____}+1} \texttt{b}^{\text{_____}}\]

Here $|w|=\text{__________} \;=2p+1\text{____}\; p$

Prover writes

\[w=(xy)z=(\texttt{a}^{\text{______}})\texttt{a}\texttt{b}^{\text{_____}}\]

i.e. $xy$ is a string of 's only

Falsifier forms

\[xy^0 z=xz=\texttt{a}^{p+1-\text{______}} \texttt{b}^{p} \not\in L\]

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\}$

GameHint

$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

\[w=\texttt{a}^{\text{______}} \texttt{b}^{p+1} \texttt{c}^0.\]

Here $|w|=\text{_______}+(p+1)+0 \;\text{______}\; \text{____}.$

Prover writes

\[w=\texttt{a}^{\text{_____}} \texttt{a}^2\texttt{b}^{p+1} \texttt{c}^0 = xyz,\]

where $xy$ can have a maximum of symbols, so $xy$ must be a string of 's only

Falsifier forms

\[xy^{\text{_____}}z=xz=\texttt{a}^{\text{______}-|y|} \texttt{b}^{p+1} \texttt{c}^{0}\not\in L\]

because $|y|\geq 1$.

This is similar to Q6.

JFLAP (Optional)¶

PL Game with JFLAP

TaskNotationHintsVideo

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}^{n-1}\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

QHint

Let $\Sigma=\{\texttt{0},\texttt{1},\texttt{+},\texttt{=}\}$, and ADD be the language given by

\[\{u\texttt{=}v\texttt{+}w\mid u,v,w\text{ are binary integers, and $u$ is the sum of $v$ and $w$ in the usual sense}\}\]

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

\[\texttt{1}^{p+d} = \texttt{0}^p+\texttt{1}^p\]

which is not correct.

Q2¶

Powers of 2

QHint

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\}$

QHint

$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!+#p||p!+#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!+--p||p!+-p-|

xykz = ap+ (k−1)|y|b------ c------|

where k = 1 + p! ∕|y|. This gives ap!+pbp! + p c p! +p which is not in the language.