Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve 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

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.