オートマトンと形式言語

まずは正則表現における代数的な法則について。集合とかでもやった例のやつだ。たとえば、交換法則とか。
次に、正則言語でないことの証明について。ここでは反復補題とよばれる、正則になるための一つの必要条件について説明があった。
要するに状態が一つ少ないときを考えて、ループのようになっているときにでも成り立つかどうかを調べればよい。頭のいい人がちゃんと考えているんだねぇ。