8

2つのオートマトン間の同等性を判断するための最良または最も簡単な方法はどれですか？

つまり、2つの有限オートマトンAとBが与えられた場合、両方が同じ言語を認識するかどうかをどのように判断できますか？

それらは両方とも決定論的または両方とも非決定論的です。

4

3 に答える 3

17

別のより単純なアプローチは、オートマトンを補完して交差させることです。オートマトンは、の補数との交点が空である場合、およびその逆の場合に含まれるiffAと同等であり、その逆も同様です。BL(A)L(B)L(B)L(A)

L(A)がに含まれているかどうかを確認するためのアルゴリズムは次のL(B)とおりです。

  1. 補完：最初にB、サブセット構造を使用して決定します。次に、すべての受け入れ状態を拒否し、すべての拒否状態を受け入れます。の補数を認識するオートマトンを取得しますL(B)。
  2. 共通部分：との補集合である言語を認識するオートマトンを構築しL(B)ますL(A)。つまり、ステップ1とのオートマトンの交差点にオートマトンを作成しAます。U2つのオートマトンを交差Vさせ、状態を持つオートマトンを構築しますU x V。内および内に遷移がある場合、オートマトンは状態(u,v)から(u',v')文字付きに移動します。受け入れ状態は、で受け入れている状態とで受け入れている状態です。au --a--> u'Uv --a--> v'V(u,v)uUvV
  3. 手順2でオートマトンを作成した後、必要なのは空をチェックすることだけです。つまり、オートマトンが受け入れる単語はありますか。これが最も簡単な部分です。BFSアルゴリズムを使用して、初期状態から受け入れ状態までのオートマトン内のパスを見つけます。

L(A)に含まれている場合はL(B)、同じアルゴリズムを実行して、にL(B)含まれているかどうかを確認する必要がありL(A)ます。

于 2012-09-27T14:09:57.200 に答える
12

2つの非決定性有限オートモタ（NFA）は、同じ言語を受け入れる場合は同等です。

それらが同じ言語を受け入れるかどうかを判断するために、すべてのNFAに最小限のDFAがあり、2つの状態が同一ではないという事実を調べます。最小限のDFAもユニークです。したがって、2つのNFAが与えられた場合、対応する最小DFAが同等であることがわかった場合、2つのNFAも同等である必要があります。

このトピックに関する詳細な研究については、「形式言語とオートマタの紹介」を読むことを強くお勧めします。

于 2011-08-01T22:15:17.320 に答える
1

私は@Guyによる答えを言い換えています。

両方で受け入れられている言語を比較するには、そのかどうかを判断するL(A) is equal to L(B)必要があります。

したがって、L(A)-L(B) and L(B)-L(A)がnullに設定されているかどうかを確認する必要があります。（理由1）

パート1：

これを見つけるために、NFAAとNFABからNFAXを構築します。

Xが空の場合は、L(A) = L(B)それ以外の場合は設定しますL(A) != L(B)。（理由2）

パート2：

今、私たちは証明または反証する効率的な方法を見つけなければなりませんX is empty set。DFAまたはNFAとしてXが空になるのはいつですか？回答：開始状態からXの最終状態に至るパスがない場合、Xは空になります。これにはBFSまたはDFSを使用できます。

理由1：両方がnullに設定されている場合は、L(A) = L(B)。

理由2：正規言語のセットが共通部分と和集合の下で閉じられていることを証明できます。したがって、NFAXを効率的に作成できます。

セットの場合：

于 2017-02-11T12:51:16.127 に答える