正規表現が正しいことを数学的帰納法で証明する(その1)

自分がTAをやっている理論系のクラスの宿題から、多くの学生がつまづいていたところを紹介解説してみます。問題をかいつまんで言うと

アルファベットa、bからなる文字列のうち、aが偶数個ある文字列にマッチする正規表現を示し、それが正しいということを証明せよ。

用語について英語日本語間の対訳は適当なのでご了承下さい。原文も並べて書きたいのですがそれはまずいかもなんでやめときます。

この記事ではMathJaxを利用して数式等を表示しています。環境によってうまく表示されない場合はパソコンやスマホのwebブラウザで表示してみてください。

more ...