Regular language?

I have a compiler question.

Determin开发者_开发技巧e whether {(ab)^n | n >= 0} is a regular language?

But I can draw its NFA. But if I use pumping lemma, I will get a contradiction answer.

Can anyone help me ?

I understand that this thread is old, but just in case this could help another student in the same situation, here is some discussion. This language is regular, and you cannot show it to be non-regular using the pumping lemma.

To see that it's regular, it suffices to produce a regular expression to generate it or an NFA to recognize it. The regular expression is trivial: (ab)*. An NFA is easy: two states; initial state accepting, other not; transition from initial to other on a; from other to initial on b. Done.

Let's see why the pumping lemma can't be used on this. To use the pumping lemma, you need to pick a candidate substring to pump. For this language, no matter how big you make the string, you will always find the following substring in a range of symbols of length at least 2: ab. Since this could always be the substring that constitutes the loop the pumping lemma says exists, there's no way to rule out that you have a regular language with (ab)* somewhere inside it, using the pumping lemma alone. (Note: for sufficiently long strings, you can't rule out the substring ba, either). Since you don't get to pick the substring that gets pumped (there are restrictions on where it can be taken, but those are put of the lemma, not something you decide), if any of the substrings work, you lose and the pumping lemma fails to demonstrate anything.

To show e.g. that L = {a^k b^k | k >= 0} is not regular using the pumping lemma, you need to pick a string for which it doesn't matter which substring you take, so long as it satisfies the hypotheses of the PL. This is why, for instance, taking a^n b^n works (all substrings satisfying the hypotheses of the PL are of the form a+, and pumping that will change the number of a without changing the number of b).