Take the 2-minute tour ×
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.

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|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
add comment

2 Answers 2

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

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.