0

2つの言語の結合のためにDFAを作成しなければならないという問題を解決しようとしています。

これらは次のとおりです。{sは{a、b、c} * | s内のすべての「a」の直後に「b」が続きます}

{sは{a、b、c} * | s内のすべての「c」の直前に「b」が付きます}

私は正しい方向に進んでいると思いますが、それが完全に正しいかどうかはわかりません。誰か見ていただけませんか？

4

2 に答える 2

1

これは、2つのDFAの和集合を見つける方法を説明する同様の投稿です。

理解するための鍵は、2つのDFAを同時に実行する必要があること、または一般に、ユニオンDFAで両方のDFAの状態を維持する必要があることです。

編集：

誤った結果が得られる理由は、DFAが決定論的ではなく、説明した言語を実際に決定しないためです。連合の計算は正しいと思いますが、先に進む前にDFAを修正する必要があります。

于 2012-05-20T16:59:10.270 に答える
0

2つの言語の共通部分は、L1 ∩ L2 = not(not(L1) ∪ not(L2))（ド・モルガンの法則によって）によって与えられます。

DFAの補集合（"not"）は、すべての受け入れ状態を非受け入れ状態に、またはその逆に変更することによって与えられます。これにより、非決定性有限オートマトン（NFA）が得られます。

ユニオンは、2つのDFAまたはNFAを組み合わせて、両方の言語を同時に受け入れる新しいNFAにすることで作成されます。これは、何も消費せずに（εのみを消費して）両方のNFAの開始状態に移行できる開始状態を導入することによって行われます。

これをすべて実行すると、NFAが得られます。一般的な方法を使用して、これをDFAに減らすことができます。

于 2012-05-20T17:07:37.770 に答える