Question

Elements of the theory of computation. Example 2.4.2

I do not understand the last sentence of the proof provided. It says that the fact that xz does not belong to L contradicts the hypothesis, but isn't it that xyz not belonging to L what we are trying to prove?

Was it helpful?

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
scroll top