When is a language regular

The pumping lemma

Theorem 313.1(Pumping Lemma, Kozen (1997) 11.2).

Let $A$ be a regular language. Then, there exists $k\ge 0$ such that for any strings $x,y,z$ with $xyz\in A$ and $|y|\ge k$, there exist strings $u,v,w$ such that $y=uvw$, $v\ne ϵ$, and for all $i\ge 0$, the string $xu{v}^{i}wz\in A$.

The pumping lemma is often used to show that certain languages are nonregular. For this purpose, we usually use it in its contrapositive form: For all $k\ge 0$ there exist strings $x,y,z$ such that $xyz\in A$, $|y|\ge k$, and for all $u,v,w$ with $y=uvw$ and $v\ne ϵ$, there exists an $i\ge 0$ such that $xu{v}^{i}wz\notin A$.

---

Ultimate periodicity of regular languages

$U\subseteq \mathbb{N}$ is said to be ultimately periodic if there exist integers $n\ge 0$ and $p>0$ such that for all $m\ge n$, $m\in U$ iff $m+p\in U$. $p$ is called the period of $U$,

Theorem 313.2(Kozen (1997) 12.3).

Let $A\subset =\{a{\}}^{\ast }$. Then $A$ is regular iff the set $\{m|a^m\in A\}$ is ultimately periodic.

fffe51

Corollary 313.3(Corollary).

Let $A$ be any regular set over any finite alphabet $\Sigma$, not necessarily consisting of a single letter. Then the set $\text{lengths }A=\{|x|:x\in A\}$ of lengths of strings in $A$ is ultimately periodic.

Proof.

Define a homomorphism$\phi :\Sigma \to \{a\}$ by $b\mapsto a$ for all $b\in \Sigma$. Then, $\phi (x)=a^{|x|}$. Since $\phi$ preserves lengths, $\text{lengths }A=\text{lengths }\phi (A)$. Also, homomorphisms preserve regularity, so $\phi (A)$ is regular. From Theorem 2, it follows that $\text{lengths }\phi (A)$ is ultimately periodic.□

---

Fooling sets

Definition 313.4(Definition).

For words $x,y$ in a language $L\subseteq {\Sigma }^{\ast }$, $z\in {\Sigma }^{\ast }$ is said to be a distinguishing suffix if $xz\in L$ and $yz\notin L$ or vice versa.

It should be clear that if $\hat{\delta }(s,x)=\hat{\delta }(s,y)$ for $x,y\in {\Sigma }^{\ast }$, then $x$ and $y$ do not have a distinguishing suffix. Taking the contrapositive, we have if $x$ and $y$ have a distinguishing suffix, then $\hat{\delta }(s,x)\ne \hat{\delta }(s,y)$.

Definition 313.5(Definition).

For a language $L$, a set of strings $x_1,\dots ,x_k$ such that $x_i$ and $x_j$ have a distinguishing suffix for all $i\ne j$ is called a Fooling set of $L$.

If $\{x_1,\dots ,x_k\}$ is a fooling set of a language $L$, and $M$ is a DFA recognizing $L$, then we have $\hat{\delta }(s,x_i)\ne \hat{\delta }(s,x_j)$ for all $i\ne j$: $M$ must have at least $k$ states.

Proposition 313.6(Proposition).

If $F$ is a fooling set of al language $L$, any automaton recognizing $L$ has at least $|F|$ states.

Thus, to prove that a language is nonregular, it is sufficient to provide an infinite fooling set.

---

References

Kozen, D. C. (1997). Automata and Computability. Springer New York. https://doi.org/10.1007/978-1-4612-1844-9