5

DFA与えられたのと同じ言語を受け入れる、最小を描画するための直接的で簡単なアプローチは何ですかRegular Expression(RE)。
私はそれができることを知っています：

Regex ---to----► NFA ---to-----► DFA ---to-----► minimized DFA

しかし、近道はありますか？のように(a+b)*ab

4

1 に答える 1

13

DFA への正規表現

正規表現 (RE) から DFA を引き出すアルゴリズムのショートカットはありませんが、派生ではなく分析によってショートカット手法が可能ですが、最小化された dfa を描画する時間を節約できます。しかし、もちろん、練習によってのみ習得できるテクニックです。私のアプローチを示すためにあなたの例を取り上げます： 

(a + b)*ab

まず、正規表現の言語について考えてみましょう。最初の試行で言語記述が何であるかを判断するのが難しい場合は、言語で生成できる最小の可能な文字列を見つけてから、2 番目に小さいものを見つけます.....

いくつかの基本的な正規表現の解法を覚えておきます。たとえば、正規表現から直接左線形および右線形の文法を作成するための基本的な考え方をここに書きました。同様に、最小化された dfa を構築するために書くことができます。

RE (a + b)*abでは、可能な最小の文字列はab、使用すると文字列(a + b)*を生成できるためNULL(^)です。2 番目に小さい文字列は、 または のいずれaabかbabです。language について簡単にわかることの 1 つは、この RE の language の文字列は常に (接尾辞) で終わるというabことaです。 b^

また、現在のシンボルがa; その場合、1 つの可能性として、次のシンボルが b文字列の終わりになる可能性があります。したがって、dfa では、 シンボルがシンボルの後にbくるたびに、dfa の最終状態の一部に移動する必要があるという遷移が必要でした。 a

次に、新しい記号が最終状態になった場合、すべての言語文字列が suffix で終了するため、後の記号は language の文字列の途中でのみ可能であるため、非最終状態に移動する必要があります。 b'ab'

したがって、この段階でこの知識があれば、以下のような不完全な遷移図を描くことができます。

--►(Q 0 )---a---►(Q 1 )---b----►((Q f ))

この時点で、理解する必要があります。たとえば、すべての状態には何らかの意味があります。

(Q 0 ) = 開始状態
(Q 1 ) = 最後のシンボルは「a」であり、もう 1 つの「b」で最終状態に移行できます
(Q f ) = 最後の 2 つのシンボルは「ab」でした

aシンボルが最終状態になったらどうなるか考えてみてください。この状態は最後のシンボルが であったことを意味するため、Q 1aを状態にするだけです。(遷移図を更新) 

--►(Q0)---a---►(Q1)---b----►((Qf))  
                ▲-----a--------|

しかし、シンボルの代わりにシンボルaがb最終状態になるとします。次に、最終状態から非最終状態に移行する必要があります。この状況での現在の遷移グラフでは、最終状態 Q fから初期状態に移動する必要があります (これも受け入れのために文字列が必要abです) 。

--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|

このグラフはまだ不完全です。aQ 1からのシンボルの出力エッジがないためです。また、aステート Q 1 のシンボルの場合、Q 1は最後のシンボルがa. 

                a-  
                ||
                ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|

これで、上のグラフのQ 1と Q fから、考えられるすべての発信エッジが存在すると思います。欠落している 1 つのエッジは、シンボル のQ 0bからのエッジです。また、状態 Q 0abには自己ループが必要です。これは、文字列を受け入れることができるようにするためのシーケンスが必要だからです。( Q 0から Q fまでは でシフト可能ab) 

    b-          a-  
    ||          ||
    ▼|          ▼|
--►(Q0)---a---►(Q1)---b----►((Qf))  
     ▲          ▲-----a--------|  
     |----------------b--------|

これで DFA は完了です。

もちろん、最初の数回の試行では、この方法は難しく見えるかもしれません。しかし、この方法で描くことを学べば、分析スキルの向上が見られます。この方法は、DFA を描画するための迅速かつ客観的な方法であることがわかります。

* 私が提供したリンクで、正規表現をいくつか説明しました。それらを学び、それらの正規表現の DFA を作成することを強くお勧めします。

于 2012-12-24T17:35:54.653 に答える