Problem 3 - Regular Languages

Prove or disprove the following statements:

1.

Let $\{ 0^n 1^n \vert n \geq 0 \} \supseteq L$. If $L$ is regular, then $L$ is finite.

2.

Let $\{ w \in \{0, 1\}^{*} \vert w = w^R \} \supseteq L$. If $L$ is regular, then $L$ is finite. Here, $(a_1 a_2 \cdots a_n)^R = a_n \cdots a_1 a_0 (a_i \in \{0, 1\}, i = 1, \dots, n)$.

1.

$L$ is regular. So, $L=L(M)$ for some finite automaton $M$ with $N$ states. $L$ is then infinite if and only if it accepts some word of length $\geq N$. Let us assume ab absurdo that we have a word $s_0\in L$ such that $\vert s_0\vert\geq N$ (i.e., we suppose that $L$ is infinite). The pumping lemma says that we can find $u_0,v_0,w_0$ such that $s_0=u_0v_0w_0$ with $\vert v_0\vert\geq 1$ and $u_0v_0\leq N$ and $\forall i\in \mathbb{N}$, $u_0v_0^iw_0$ is in $L$. $s_0$ will be of the form $0^k1^k$ and it means in particular that $v_0$ has the form $0^l1^l$ (if it is not the case, it cannot be pumped, and we have a contradiction with the fact that $L$ is regular). The pumping lemma then says that $L$ contains the word $0^{k-l+il}1^{k-l+il}$ and the number of 0's (together with the number of $1$'s of course) may grow until it is greater than $N$. Let suppose that $w_1$ is such a word. With the same instance of $N$ as before, we can find a new decomposition $s_1 = u_1v_1w_1$ which satisfies the same criteria. But then it yields a contradiction with the fact that $L$ is regular because, since $\vert u_1v_1\vert\leq N$, $v_1$ cannot be pumped without yielding a word that is not in $L$! We conclude that such a word $s_0$ doesn't exist and therefore that $L$ is finite.

2.

$L$ is regular. So, $L=L(M)$ for some finite automaton $M$ with $N$ states. $L$ is then infinite if and only if it accepts some word of length $\geq N$. Let us assume ab absurdo that we have a word $s_0\in L$ such that $\vert s_0\vert\geq N$ (i.e., we suppose that $L$ is infinite). The pumping lemma says that we can find $u_0,v_0,w_0$ such that $s_0=u_0v_0w_0$ with $\vert v_0\vert\geq 1$ and $u_0v_0\leq N$ and $\forall i\in \mathbb{N}$, $u_0v_0^iw_0$ is in $L$. $s_0$ will be a palindrome. Let assume that $s_0$ can be noted $rr^R$. The fact that $s_0$ can be pumped means that $v_0$ has a even number of symbols which form a symmetric word. We can then pump it until it reaches a palindrome $s_1$ whose length is $\geq 2N$. By applying the pumping lemma with the $N$ integers, we are given a decomposition for $s_1$: $u_1v_1w_1$. As $\vert u_1v_1\vert\leq N$, any attempt to pump will yield a word that is not a palindrome and therefore is not in $L$, a contradiction. We conclude by saying that the assumption that $L$ is infinite is absurd.