# Proving the language is regular or not?

I was trying to solve these two questions for a while, can I know how can I use pumping lemma to solve them?

a) $\{a^i b^j \mid i, j \geq 0 \text{ and }i + j = 5\}$.

b) $\{w = xy \mid x, y \in \{a, b\}^* \text{ and } |x| = |y| \text{ and } \#a(x) \geq \#a(y) \}$.

and thanks

• Welcome to SE network, please visit Help Center Jan 5 '17 at 13:44
• Did you really try seriously to solve a) ? Jan 5 '17 at 14:00
• @J.-E.Pin I did try and I solve it, I found similar question but with (i doesnt equal j) Jan 7 '17 at 15:44

Language a) is regular.

To see this, observe that there are only finitely many strings in this language (all strings of length $5$ such that the string is composed of zero or more $a$s followed by zero or more $b$s). Thus, we can compose a DFA, which has a finite number of accepting states corresponding to these strings, and all other states are not accepting. In general, any finite language is regular.

Language b) is not regular.

To see this, we need to use the pumping lemma. Suppose language b) was regular, and was the language corresponding to some DFA $D$, which has $N$ states. The pumping length of this language must be $\leq N$.

Clearly, $w = b^{N+1}ab^{N+1}a$ is part of this language. Using the pumping lemma on $w$, we need to decompose $w=xyz$, where $|xy|\leq N$ and $|y|\geq 1$. The only way this can happen is if $y=b^i$ for some $i\geq 1$. Then, by pumping $w$, we see that $xy^2z=b^{N+1+i}ab^{N+1}a$ must be in this language, but it is not as the first half of the language contains only $b$s but the second half has at least one $a$.

This is a contradiction, and hence the assumption that language b) was regular is false.

• can you help me in composing the dfa? because I should use pumping lemma first to prove then draw the dfa if its possible Jan 7 '17 at 15:49
• + isn`t this the same as my question, L = {a^ib^j: i, j >= 0 and i not equal j} Jan 7 '17 at 15:52