[解決済み] 2つのNFAの交点の求め方

質問

DFA では、2 つのオートマトンの状態の積をとり、両方のオートマトンで受理されている状態を受理することで、2 つのオートマトンの交差を行うことができる。 Unionも同様に行います。しかし、NFAではイプシロン遷移を使って簡単に和集合を作ることができるが、その交差点はどのように行うのだろうか？

どのように解決するのですか？

NFAに対してもDFAと同様に積和演算を用いることができる。唯一の違いは、ε-遷移をどう扱うかである。具体的には、各状態(q <サブ i , r <サブ j ) を持つクロスプロダクト・オートマトンにおいて、その状態からのε-遷移を、それぞれの状態 (q _k , r <サブ j からのε-遷移がある場合。 _i からq <サブ k と、各状態の組（q <サブ i , r <サブ k からのε-転移がある場合。 _j からr <サブ k .

あるいは、常にNFAをDFAに変換し、そのDFAのクロスプロダクトを計算することができます。

お役に立てれば幸いです。