2008-06-16から1日間の記事一覧

ポンピング補題の練習

CS

B1-2向け.DFA用のポンピング補題は割と簡単に証明が出来ます. 状態数以上の文字列をDFAに入力として与えたときには, 鳩ノ巣原理より, 必ずどこかの状態を2回通っているということが直観です. 反復補題とも言われる様子 (→正規言語の反復補題 - Wikipedia)ポ…