Prove $\{a^ib^i\mid i\ge0\}$ is not regular using the pumping lemma
-
29-09-2020 - |
Solution
By the pumping lemma $a^n b^n$ can be written as $xyz$ with $|xy| \le n$ and $|y| \ge 1$ in a way that ensures that $xy^kz \in L$ for any $k \ge 0$. Picking $k=0$, this implies that $xz \in L$.
Since this is not the case for your language $L$, you know that $L$ cannot be regular.
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange