トップ > 計算理論 > テスト勉強

テスト勉強

計算理論

自分用メモ。ビデオアーカイブを見直しつつ、過去問を見つつ、できるようになっておかないと死亡なトピックをまとめておく。

具体的に解釈された言語 => DFA

具体的に解釈された言語 => 正則言語

NFA => DFA

スライドのp51からp63に。p59からが例になっていて分かりやすいはず。5つのステップを考えていく。

  • (1)のステップで\epsilon動作で行けるところを忘れないこと
  • 初期状態は\epsilonで行けるところも含めて考える

p65の(b)のところをちゃんと書きくだせるようになっておくこと。\emptysetの状態についても忘れないこと。

DFA => 正則言語

計算理論の基礎のp82とp83の練習問題が丁度よい感じに載っている。スライドのは初期の状態が簡単なものばっかりで試験で死ぬ感じなので

  • 初期状態にループがある
  • 受理状態が複数ある

ケースについて、ちゃんとできるようになっておいたほうがいい。

パンピングレンマ

計算理論の基礎のp88からいくつか例が載っているので、その辺で証明のカンをつかんでおこう。

語の選択がポイント。語を選択すると本当は正則じゃないんだけど、背理法で矛盾が導けなかったりするので注意が必要。

やっておくべき問題。

  • 例7.2
  • L = \{a^n b^n | n \geq 0\}
  • L = \{a^n b^n | n \leq 0\}
  • L = \{a^m b^n | m \neq n\}
  • L = \{ww | w \in \{a, b\}^*\}
  • L = \{w a^n | w \in \{a, b\}^*, |w| = n\}
  • L = \{a^n w| w \in \{a, b\}^*, |w| = n\}
  • L = \{a^{k^2}| k \geq 0\}
  • L = \{a^n b^n | n \geq 0\}が正則でないのを利用して、他の言語が正則でないことをパンピングレンマ使って示す、というようなのも練習が必要

正則言語に関する判定問題

等価な最簡形のDFAの求め方

p127以降のところ(DFAの簡単化)。同値類についてまとめてあげる。ここは簡単。