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?
On
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.
HINT: Apply the pumping lemma to the word $x^py^{p+2}$, where $p$ is the pumping length.