2

私はこれについてグーグルで調べましたが、本当に決定的なものは何も表示されませんでした。

A と B の 2 つの言語があるとします。

A = { w は {a,b,c}* のサブセットで、w の最後の文字から 2 番目の文字は b です }

B = { w は、最後の文字が b であるような {b,d}* のサブセットです }

これをどのように定義しますか？アルファベットは両方の結合で {a,b,c,d} になると思いますが、それ以外は、これの DFA を作成する方法がわかりません。

誰かがこれに光を当てることができれば、それは素晴らしいことです.

4

1 に答える 1

3

集合論の観点から見ると、各言語は、いくつかのアルファベット Σ 1および Σ 2の文字列のセットにすぎません。2 つの言語が交差する場合、結果セットに含まれる可能性のある唯一の文字列は、Σ 1 ∩ Σ 2の文字で構成される文字列です。これは、そのセットに含まれない文字は純粋に 1 つのセットの文字列に属している必要があるためです。

このための DFA を構築する方法については、まずこの質問に答えることから始めることをお勧めしますが、アルファベット Σ に対する通常の言語 L が与えられた場合、その DFA を言語 Σ ∪ { x } (ここで x ∉ Σ) を持つように変更するにはどうすればよいでしょうか? これを行う 1 つの方法は、Σ ∪ { x } のすべての文字にそれ自体への遷移を伴う新しい「デッド ステート」を追加し、DFA のすべての状態から文字 { x のデッド ステートへの遷移を追加することです。 }。これを使用して、Σ 1と Σ 2の元の言語の DFA を変換して、アルファベット Σ 1 ∪ Σ 2を持たせることができます。これが完了したら、通常のアルゴリズムを使用して 2 つの DFA を交差させて交差を計算し、2 つの言語の交差に対する DFA を取得できます。

お役に立てれば！

于 2013-03-05T01:09:03.133 に答える