言語が他の言語との望ましい交差点を持つ最小限のDFAを見つける

私が規則的な言語$ B subseteq A $を、対応する(既知の)最小確定的有限オートマトン$ M_A、M_B
$でもっているとします。

$ M_C $($ C $に対応する最小限のDFA)のサイズを最小限に抑える$ B = A cap C
$のような別の通常の言語$ C $を探したいと思います。

一般に、$ M_C $は$ M_B $よりずっと小さくなります。例えば$ B $に偶数長の$ A $の文字列を置くと、$ M_C
$は2状態のマシンになりますが、$ M_B $は$ M_A $ほど複雑であるかもしれません。

これは、既存のオートマトン最小化アルゴリズムを簡単に適用する必要があるように感じますが、もしそうなら、私はそれを見ません。

どのように見えるかは、Myhill-Nerode定理のアナログを使って文字列を区別しようとすることです。それは、$ x、y
$が$問題は、対応する区別不可能な関係はもはや推移的ではない(私は思う) – $ b $と区別がつかない$ a
$が与えられていると仮定すると、問題は次のようになる:A $ではなく$ xs $ c $のような$ s
$が存在するかもしれませんが、B $のB neq cs ではA $の$ s、c $はA $の$ bs not $ a
$と$ c $を区別するために使用されます。

通常のDFA最小化とは異なり、$ M_C $が一意であると期待する理由はありません.2つの非等価なマシンは、$ C neq
C ‘$を表すことができ、$ A cap C = A キャップC
‘$。それらのあいまいさは問題ではなく、あなたはただそれらを任意に解決することができますが、私はそれを自分自身に確信させることができませんでした。

そのようなオートマトンは最大で$ | M_B | $のサイズを持つため、対応する決定問題はNPにあるので、問題は少なくとも
“合理的に扱いやすい”ものであり、与えられたオートマトンが状態$ M_A times M_B
$を持つ交差オートマトン、および等価性のテストは$ P $にあります。
SATやILPには、私がまだ解決していない素晴らしい変換があります。これは、より良い解決策を望んでいるからです。

これはよく研究された問題ですか?それとも1つに減らすことができますか?

ベストアンサー

$ M_C $は$ S ^ + = B $のすべての単語を受け入れ、$ S ^ – = A setminus B
$のすべての単語を拒否しなければなりません。

$ A ^と$ B $が有限で、$ S ^ + $と$ S ^ – $の両方が空でないようにします。 $ M_C
$の正確な計算はNP困難です。 [1]

[1] E.M.Gold。与えられたデータからのオートマトン識別の複雑さ。
情報と管理、37、302-320(1978)

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です