# Proving this language is regular?

Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language?

I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, could someone show me the transition graph/table? If not how do i prove this question?

-
You could start here to learn how to get mathematics to display properly at MSE. – Brian M. Scott Feb 13 '13 at 6:27
Are you satisfied with one (or both) of the answers? If so, please accept one, or if not, please indicate what you still don't understand. It would be nice if you could do the same for your other questions as well. – Tara B Feb 15 '13 at 18:00

## 2 Answers

HINT: Apply the pumping lemma to the word $x^py^{p+2}$, where $p$ is the pumping length.

-

The Myhill-Nerode theorem settles this immediately.

If you assume that a DFA for the language exists, then which of the prefixes $x$, $x^2$, $x^3\ldots$ could possibly lead to the same state? $\{w\mid x^nw\in L\}$ and $\{w\mid x^mw\in L\}$ are always different when $n\ne m$ -- in fact always disjoint.

-