Is this language regular? {a^i b^j| i=j mod 19}

Question

I know that {a^i b^j | i = j } is not regular and I can prove with pumping lemma; similarly I can use pumping lemma to prove this one not regular too. But I think I see some similar problem that says such language is actually regular. And because I'm not confident about my knowledge in pumping lemma I'm asking this bad question. Sorry.

This is how I prove it: let w be a^p b^(19k+p) , clearly this is in the language. Then if I pump a, making it a^(p+1) b^(19k+p) . It fails. Therefore, it's not regular.

Is my proof right?

Answer 1

Take a look at this answer. In short, you're not pumping the string correctly. The pumping lemma states that your string w can be divided as w = xyz where |xy| ≥ p, and y is not empty. You can then pump the string as xyⁱz for all i ≥ 0.

The key here, is that the pumping lemma states that there exists a division of the string w satisfying these properties, you do not get to choose the division, and that you can only pump the string as xyⁱz.

However, this language is regular, so the pumping lemma can't be used to prove if a language is regular, it can only prove if a language is irregular (it's a necessary but not sufficient condition). To show that a language is regular you can construct a DFA, NFA or regular expression that describes your language exactly. One such regular expression is:

(a^19)*(e|ab|aabb|aaabbb|...|a^18b^18)(b^19)*

where e is the empty string.

---

I suspect that your language is an example from an introductory course in automata or computation. If you're interested, the Myhill-Nerode theorem is not often covered in introductory material, but in this case offers a very easy proof of regularity: consider the distinguising extensions b, bb, bbb, ..., b^19 and the proof follows relatively easily from that.