まずは、正則言語のクラスはどのような演算について閉じているかというもの。今回は補集合と積集合は正則言語で完全に表現が可能であり、閉じていることを証明した。
次に、決定問題。今回は「空言語判定」という問題。とくに非決定性オートマトンが与えられていた場合に正則言語が存在するかどうかという判定を行う問題について、そのようなアルゴリズムがあるかというものを扱った。これはグラフ理論における到達問題と同じようなもので、ステップを繰り返すことで、到達できる状態の数が増加しなくなったときに、最終状態の集合がその状態の数に含まれているかどうかということを調べるものである。ただ、問題となるのは効率であって、解けるかどうかということはそれほど問題ではないということもおっしゃっていた。
しかし私が問題だと思うのは、どこまでいけば、到達できる状態の数が打ち止めになるのか、つまり増加しなくなるのかということがわかるのだろうかということだ。何か指針があるのか？謎だ。
で、ここで正則言語はおしまい。次は文脈自由文法(Context Free Grammer)について。これまでの正則言語では扱うことのできなかった言語について拡張を行い、機械も決定性オートマトンからプッシュダウンオートマトンに進化する（ようだ。まだしらないので。）
で、簡単にどのようなものか聞いたが、文脈自由文法はBNF（バッカスナウアーフォーム）っぽい。よっしゃぁ！これは、かなり得意で、情報処理技術者試験では得点源だったから、余裕かも・・・と思った。
ちなみに文脈依存文法(Context Sensitive Grammer)というものもあり、これは文脈によって、つまり前後の要素の影響を受けて文法が構成されるもののことらしい。たとえば、英語の三人称単数現在のSは典型的な 文脈依存文法の例だということだ。なるほどね。
