Subscribed unsubscribe Subscribe Subscribe

ろじかるんるんものがたり

病人が特に何も書かない。無駄だからだ。

オートマトンと正規表現のお勉強

計算理論の基礎 1 オートマトンと言語を買っていただいたので、少しずつ読んでいる。

計算理論の基礎 [原著第2版] 1.オートマトンと言語

オートマトン正規表現も、齧ったことは何度もあるけれど、きちんと学んだことはなかった。
真っ当な情報系の学部を出ていれば普通はこのくらいの知識は持っているはずだろうけれど、真っ当とはいえない情報系の学部にいたし、卒業もしなかった。
最初は雑に読んでいたんだけれど、丁寧に読んだ方がいいなと思って読み直している。ついでに折角なので記録を取ろうと思う。

以下、メモ。

ちょっと理解に戸惑った箇所についてまとめ。二つの言語に対する連結演算の結果として、空列を受理する明らかに無駄と思われる状態が導入される。例えば p79 の正規表現 ab の例における空列を受理する状態等。これは演算の対象となる言語 A1, A2 それぞれの受理状態と開始状態を仮に q1, q2 とすると、q1 と q2 を等しいとするような操作はないので、新しく状態を導入することで連結を実現している。p71 の遷移関数の上から三番目がこの導入(された状態の遷移)に相当する。

p79 の NFA と等価な最小の NFA について "読者は、それを見つけられるだろうか?"とあるが、

で多分あってるはず… a* から考えて (ab⋃a)* について考えれば割と自明。

追記:
メモを公開すると厳しい突っ込みが入る。

ということで

二つの言語に対する連結演算の結果として、

同じΣを持つ任意の NFA N1, N2 を受理する正規言語 A1, A2 について、A1, A2 の連結演算の結果として~

とかで、以降も同じ。