Using Pumping Lemma to prove that $L=\{a^mb^{3m}:m\in\mathbb{N}\}$ is not recognizable over $A=\{a,b\}$

464 Views Asked by At

[Pumping Lemma]: Let $\mathcal{A}=(Q,A,\cdot,i,T)$ be a (complete and deterministic) automaton and let $L=L(\mathcal{A})$ be the language recognized by $\mathcal{A}$. If $L$ is infinite and $\mathcal{A}$ is finite with $card(Q)=n$, given $w \in L$ such that $|w|=m \geq n$, there exist $u,v \in A^*$, $z \in A^+$ such that $|u|<n$, $|z| \leq n$ and $uz^pv \in L$ for all $p \in \mathbb{N}_0$.

Prove that $L=\{a^mb^{3m}:m\in\mathbb{N}\}$ is not recognizable over the alphabet $A=\{a,b\}$.

Attempt: Let $\mathcal{A}$ be a deterministic and complete automaton with $n$ states that recognizes $L$. Let $w \in L$ such that $|w|=l \geq n$. Since $w \in L, w=a^mb^{3m}$ for some $m \in \mathbb{N}$. Then $l=m+3m=4m$. By Pumping Lemma, there exist $u,v \in A^*, z \in A^+$ such that $w=uzv, |u|<n, |z|\leq n$ and $uz^pv \in L$ for all $p \in \mathbb{N}_0$. What can I say next? Thanks!

1

There are 1 best solutions below

8
On BEST ANSWER

HINT: Take $m=2n$, so that $w=a^{2n}b^{6n}$. Then the lemma tells you that $w$ can be decomposed as $uzv$ in such a way that $|u|<n$, $|z|\le n$, and $uz^pv\in L$ for all $p\ge 0$. Notice that this implies that $|uz|<2n$, so $uz$ must be part of the string of $a$s in $w$. What happens now if you take $p\ne 1$? Is it actually still true that $uz^pv\in L$? In other words, does $uz^pv$ have exactly three times as many $b$s as $a$s?