不完全なDFAのクロス積

Question

2つのDFAの間でクロス積をしようとしていますが、どちらも不完全なDFAです。

次の画像は、2つの不完全なDFA間のクロスプロダクトの交差点に出てきた答えです。アルファベットは{a、b、c、d、e}です。

それは正しいですか、彼らが不完全なすべてのものを変更しているという事実のでしょうか？

Answer 1

あなたが組合を見つけるためにクロスプロダクトを構築している場合、それらが不完全であるという事実はあなたの仕事を変えます。ただし、交差点ではこの基本的なアプローチを使用できます。しかし、あなたはいくつかのエラーをした：

左上に開始し、状態A1のうち、全ての遷移を見てレッツ：

まず、あなたは状態遷移が状態A1から状態A2にcのラベルが付いています。ただし、AからAへの遷移が、最上部のDFAにはcというラベルが付けられていないため、正しくありません。次に、状態A1からそれ自身に移行するaのトランジションがあります。状態1からaと表示されているものへの遷移がないため、これも間違っています。同様に、状態1bからの移行がないので、A1からB1への移行も無効になります。不完全なのDFAと協力して、このようなクロス製品を作るときの状態pと状態qの両方がために、発信エッジを持っているという手紙があるとき

、あなただけの状態(p,q)の発信エッジを持っています。

したがって、開始状態からの遷移はありません。現時点では、開始状態からの遷移がないため、ポイントはありません。結果として得られるDFAは何も一致しません。

これにアプローチする方法のもう1つの可能性は、非受理状態を追加することによって両方のDFAを最初に完成させることです（私はこの状態を∅と呼んでいます）。この状態は、既に異なる出力エッジが存在しないすべての文字について、すべての状態からそれに向かうエッジを有するべきである。たとえば、最初のDFAでは、Aから∅までのc,d、およびeのエッジがあります。また、すべての文字に対して、∅から∅までのエッジが存在する必要があります。両方のDFAが完成しました。

あなたがこれを行うと、あなたがに行くA1のうちエッジで終わる：aためA∅、bためB∅、cため∅1、そしてdとeため∅∅。残りは練習問題として残されていますが、完全に描画すると、A1から受け入れ可能な状態に至るパスがないことが再度確認されます。

最初に両方のDFAを完成させることは、クロス積を構築するためにクロス積を作成している場合は、∅に達してからいずれかのDFAに∅という状態をスローするだけです∅を含むいくつかの州がクロス積の状態を受け入れている可能性があるため、受け入れ国には決して到達しないことを意味しますが、組合ではそれを保持する必要があります。 （まだ∅∅の状態とそれにエッジを捨てることができます）