computer-scienceregular-languagefinite-automatafsmformal-languages

Why is {a^nb^n | n <= 10} regular?


I understand that { an bn | n>=1 } is not regular using Pumping Lemma.

But then, how is { an bn | n<=10 } regular? I thought we couldn't store the number of a and b in an automata. And I couldn't verify it with pumping lemma too.


Solution

  • Every language that has a finite number of strings as members is regular, because you can construct a finite automaton that accepts each of these strings.

    You can prove it by just constructing the automaton. It has a finite number of states and by the Myhill–Nerode theorem all of the strings this automaton accepts belong to a regular language.