# Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not? [duplicate]

Is $L=\{ a^nb^m \mid n,m \ge 0, n\ne m\}$ a regular language?

I think it is but can't prove it.

-

## marked as duplicate by Ran G., A.Schulz, Luke Mathieson, Gilles♦Nov 19 '12 at 22:15

see this question cs.stackexchange.com/q/4752/157 – Ran G. Nov 14 '12 at 6:46

Using Ran G.'s comment which links to a very similar question:

Suppose $L$ is regular. $M=a^*b^*$ is regular, too, so since regularity is closed by set difference, $M\backslash L=\{a^nb^n\}$ would be, too, which is the usual counterexample.

-

The comment of Patrick87 correctly points out the flaw in my "proof" below, but I let it be as it were as it might be a good starting point. Together with his comment, it should be simple to prove that the language is not regular.

First you should know that a language $L$ is regular if and only if its complement is regular. This is fairly simple to prove, given a deterministic finite automaton $M$, let $M^{-1}$ be the automaton where a state is accepting if and only if it is not accepting in $M$.

Given this theorem you should be able to prove that since $L$ is the complement of the classic non-regular language, $L$ is not regular either.

(Handwaving: A language is usually not regular if you need to count stuff in a word to determine whether or not a word belongs to the language. You can, for any constant $k$ count stuff with respect to $k$, like modulo, $\leq$ etc, but in your example you need to be able to count to $m$ and $n$ for any $n$ and $m$.)

-
Minor nitpick: $L$ isn't really the complement of any "classic" nonregular language, right? $L$ is the complement of the language "Any string of $a$s and $b$s where either there are some $b$s before $a$s or the number of $a$s is equal to the number of $b$s." – Patrick87 Nov 14 '12 at 16:30