is this language regular or not?

Question

I have problem with this language

$$L = \{ a^n b^m : \text{$n+m$ is odd} \}$$

is it regular or not

My Solution

I used pumping lemma,

w = a^2p b^2p+1 (the same for a^2p+1 b^2m )

$$\begin{aligned} w &= a^{2p}b^{2p + 1} & \text{[same for $a^{2p + 1}b^{2m}$]}\\ y &= a\\ xy^{2z} &= a^{2p + 1}b^{2p + 1} \end{aligned}$$

$2(2p+1)$ is even number so this is contradiction ? and language is not regular

but my friend's solution is :

$$\begin{aligned} L = \{a^n b^m: \text{$n$ is odd, $m$ is even}\} \cup \{a^n b^m: \text{$n$ is even, $m$ is odd}\} \end{aligned}$$

and

$\{a^n b^m : \text{$n$ is odd, $m$ is even}\}$ is regular

$\{a^n b^m : \text{$n$ is even, $m$ is odd}\}$ is regular

so $L$ is regular, how it can be solved ?

Answer 1

Your friend is correct; $L$ is indeed regular. Recall that the Pumping Lemma goes like this:

Pumping Lemma: If $L$ is a regular language defined by some DFA on $p \geq 1$ states, then any string $w \in L$ with $|w| \geq p$ can be written as $w = xyz$, where $|xy| \leq p$, $|y| \geq 1$, and for any $i \geq 0$, $xy^iz \in L$.

You chose $w = a^{2p}b^{2p+1}$, which certainly satisfies the condition that $w \in L$ and $|w| = 4p+1 \geq p$. So by the Pumping Lemma, we have $w = xyz$, where $|xy| \leq p$, $|y| \geq 1$, and for any $i \geq 0$, $xy^iz \in L$. Hence, we must have $y = a^k$ for some $k \in \{1,\ldots,p\}$. Notice though that we have no control over this value of $k$.

Continuing with your work, you chose $i = 2$. Then we know that $xy^2z = a^{2p+k}b^{2p+1}$ must be in the language. This is not an immediate contradiction because if $k$ is even, then we certainly have that $xy^2z \in L$.