Why doesn't {a^nb^n | n >= 0} follow regular language closure properties?

132 views Asked by At

Using the pumping lemma, we can prove that {a^nb^n | n >= 0}, but what is not clear is the following.

{a^n | n >= 0} is regular by itself and so is {b^n | n >= 0}, and if I am not mistaken, regular languages are closed under concatenation, so why doesn't {a^nb^n | n >= 0} follow this rule?

1

There are 1 answers

0
Nikolay Handzhiyski On

The n in {a^n | n >= 0} is not the same as the n in {b^n | n >= 0}. After concatenating them you get {a^jb^k | j,k >= 0} that is regular. It is not the same as {a^nb^n | n >= 0} (or to say {a^jb^k | j,k >= 0; j=k}) where the repetitions of a and b are the same number.