Why {a^nb^n | n>=1} is not a regular language?

Question

I was following this video, and wonder why {aⁿbⁿ | n≥1} is not a regular language?

enter image description here

You are confused if you think that the diagram you show recognizes a^nb^n — Pascal Cuoq, Apr 06 '15 at 19:51
@Blake After two fellow StackOverflow users have spent time answering? How unneighborly! — Pascal Cuoq, Apr 06 '15 at 19:52
@PascalCuoq that is to avoid more users spending time reading my mistake — Blake, Apr 06 '15 at 19:55
@Blake read [What is basically a regular language? And why an infinite language `a*b*` is regular whereas languages like `{ anbn | n > 0 }` are not regular](http://stackoverflow.com/questions/16723185/is-ab-regular/16730707#16730707) — Grijesh Chauhan, Apr 07 '15 at 11:53
Why not accept one of the answers; this will save more users from answering also.... — Brian Tompsett - 汤莱恩, May 20 '15 at 13:25

score 0 · Answer 1 · answered Apr 06 '15 at 19:47

0

Regular language must be recognized by finite automaton. As n is not bounded by any constant the automaton cannot be finite.

answered Apr 06 '15 at 19:47

Grzegorz Żur

44,524
14
110
102

score 0 · Accepted Answer · answered Apr 06 '15 at 19:48

If you take the definition of “regular language” as “recognized by a finite automaton”, let m be the number of states of such an automaton. If the automaton is to recognize a¹b¹, a²b², …, a^m+1b^m+1, the states of the automaton cannot be the same after it has read a¹, a², …, a^m+1, leading to a contradiction.

Why {a^nb^n | n>=1} is not a regular language?

2 Answers2