2

これは、研究プロジェクトの DFA です。DFA は手動で作成しました。DFAに対応した正規表現とは何かに興味があります。確かに、それに対応する複数の正規表現が存在する可能性があります。私たちはよりシンプルなものを好みます。

ここに画像の説明を入力

4

4 に答える 4

1

B と E のセルフ ループでDFAのラベルを見逃してい0ます。

DFA の正しい正規表現は次のとおりです。

(00* 10*1)* (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1  ( 0 + 10)* 1 1)*

簡単な説明:

  1. である最終状態は 1 つだけですD。そのため、文字列が で終わる場合は受け入れられますD。着信エッジDがラベル付けされ1、ラベル付けさDれた自己ループがあることに気づきましたか0。

  2. 開始状態は、文字列をまたは でA開始できるようにするためです。実際には、A には 2 つのループがあり ます。 上部ループの RE は次のとおりです。 010
    00* 10*1

    これを理解するには：

      0     0*           1      0*            1  

 A-E   loop on E     E-F    loop on F     F-A

  3. 下のグラフのからAに移動します。DREは1 (0 + 10)* 1 1
    これを理解するために：

     1        (0 + 10)*    1     1
 A - B    loop on B    B-C   C-D

  4. DFA の完全な RE は次のとおりです: ( answer ) 

    (00* 10*1)* (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1  ( 0 + 10)* 1 1)*

    これを理解するには：

    (00* 10*1)*  (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1 ( 0 + 10)* 1 1)*

^             ^                                                    ^   
upper loop    A to D           loop on D              * for loop on D    


                      ( 0 +  1    (00* 10*1)* 1    (0 + 10)*   1  1  )*
                        ^    D-A   A-A        A-B  loop on B, B-c c-D       
                     self loop on D

@RedBaronがコメントしたように編集すると、この正規表現は文字列を生成します01110100110：

最初のチェックは、DFA によって受け入れられるかどうかです。

A--0--> E--1---> F--1---> A---1---> B--0---> B---1--->C ---0--- ->B---0---> B--1-->C---1---> D---0--->D‌ </p>

はい、文字列は DFA で受け入れられます。

RE から生成する方法 回答で示しました。以下に RE と文字列を配置しました。

(00* 10*1)*    (1(0 + 10)* 1 1) ( 0 + 1 (00* 10*1)* 1 ( 0 + 10)* 1 1)*

 0^  1^ 1      1  0100     1  1   0

あなたが理解しなければならないかもしれない難しさだけ：どのように(0 + 10)*生成され0100ますか？以下のこのチェックについて：

(0 + 10)*3回繰り返す：

(0 + 10)(0 + 10)(0 + 10)
 0           10  0
于 2013-03-29T16:39:07.360 に答える
0

使用する必要があるアルゴリズムについては、こちらで説明しています。このトピックにもっと興味がある場合は、 Michael Sipser のIntroduction to the Theory of Computation を読むことを強くお勧めします。

特定の DFA の場合、アルゴリズムに従って次の正規表現を取得します。

[(010*1)*1(10*)110*1]*(010*1)*1(10)*110*
于 2013-03-29T05:54:23.770 に答える
0

ジャック、基本的にこの DFA には 2 つの正規表現があります。1 つ目は AB*CD*A、2 つ目は AE*F* です。

于 2013-03-29T05:28:21.933 に答える
0

10*110*cB のループなしで ABCD から遷移するためのものです。

1(0*(10)*)*110*CとBの間のループもカバーしていると思います

0+10*1AEF からのループです。したがって、両方の式にプレフィックスを付けることができます

(0+10*1)*10*110*ループなしでもループあり(0+10*1)*1(0*(10)*)*110*でも取得できます

したがって、最終的な表現は

(0+10*1)*1(0*(10)*)*110*

AからDへの移行用

最終的に状態 D に到達すると、 を取得し1、到達Aして、すべてをもう一度繰り返すことができます

((0+10*1)*1(0*(10)*)*110*)(1((0+10*1)*1(0*(10)*)*110*))*

この DFA の有効な文字列と無効な文字列の実際の動作を確認してください

明確化- この正規表現は、PCRE で受け入れられている正規表現に基づいています。So+は文字列が 1 回以上出現することを*意味し、0 回以上出現することを|意味します。OR

編集は、次の(0*(10)*)*ように書くことができます(0|(10))*（その方向に私を向けてくれた@grijesh-chauhanに感謝します）。したがって、RE (PCRE ベース) は次のようになります。

((0+10*1)*1(0|(10))*110*)(1((0+10*1)*1(0|(10))*110*))*
于 2013-03-29T05:35:36.723 に答える