Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Possible Duplicate:
Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

see this question –  Ran G. Nov 14 '12 at 6:46

2 Answers 2

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.

share|cite|improve this answer

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$.)

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

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