オートマトンと正規表現のお勉強
計算理論の基礎 1 オートマトンと言語を買っていただいたので、少しずつ読んでいる。
オートマトンも正規表現も、齧ったことは何度もあるけれど、きちんと学んだことはなかった。
真っ当な情報系の学部を出ていれば普通はこのくらいの知識は持っているはずだろうけれど、真っ当とはいえない情報系の学部にいたし、卒業もしなかった。
最初は雑に読んでいたんだけれど、丁寧に読んだ方がいいなと思って読み直している。ついでに折角なので記録を取ろうと思う。
以下、メモ。
ちょっと理解に戸惑った箇所についてまとめ。二つの言語に対する連結演算の結果として、空列を受理する明らかに無駄と思われる状態が導入される。例えば p79 の正規表現 ab の例における空列を受理する状態等。これは演算の対象となる言語 A1, A2 それぞれの受理状態と開始状態を仮に q1, q2 とすると、q1 と q2 を等しいとするような操作はないので、新しく状態を導入することで連結を実現している。p71 の遷移関数の上から三番目がこの導入（された状態の遷移）に相当する。
p79 の NFA と等価な最小の NFA について "読者は、それを見つけられるだろうか？"とあるが、
オートマトンの気持ちになってる。 pic.twitter.com/bpweGka6to
— りりかるろじかる (@lyrical_logical) December 10, 2016
で多分あってるはず… a* から考えて (ab⋃a)* について考えれば割と自明。
追記：
メモを公開すると厳しい突っ込みが入る。
@lyrical_logical あと「言語」は列の集合のことであってそれを定義するオートマトンのことではないので、言語について受理状態と言っても意味が通らないと思います。読んで分からない文章ではありませんが、厳密な議論を展開する上でまずは用語を正しく理解することが重要でしょう🙆
— 坂口和彦@C91 1日目 西み-28a (@pi8027) December 10, 2016
ということで
二つの言語に対する連結演算の結果として、
は
同じΣを持つ任意の NFA N1, N2 を受理する正規言語 A1, A2 について、A1, A2 の連結演算の結果として～
とかで、以降も同じ。
