Pumping lemma contradiction

Question

I have to prove that the language $A_{1}= \{\alpha \in \Sigma^{*}|c^{a}(\alpha)>c^{b}(\alpha) \}$ where $\Sigma=\{a,b\}$, where $c^{a}(a)$ means the number of $a$ in $\alpha$, and $c^{b}(\alpha)$ means the number of $b$ in $\alpha$, is non-regular. I tried something like this $\alpha=a^{p+1}b^{p}$ and $y=a^k$ and pump from there, but it isn't working.Any ideas how to solve it ?

Answer 1

Let's suppose that the language $A_1$ is regular. Let $p$ be the pumping length. As you did, take the word $\alpha=a^{p+1}b^{p}$.

According to the pumping lemma, $\alpha$ can be separated into $xyz$, such that the conditions of the lemma are satisfied. According to the condition $|xy| \leq p$, $y$ contains only $a$.

According to the lemma, the word $xy^iz \in A_1, \forall i \geq 0$.

So $xy^0z=xz$ should be in the language. With the substraction of the part $y$, the number of $a$ in $\alpha$ is getting smaller.

$\alpha$ has only one $a$ more than $b$, so $xy$ cannot contain more $a$ than $b$, so it is not in $A_1$.

So you have the contradiction.