1

タイトルが示すように、DFA と NFA は正規表現とどのように関連していますか? DFA と NFA を学ぶことは、正規表現をよりよく理解するのに役立ちますか?

4

2 に答える 2

3

有限オートマトン (fa)、正規表現 (re)、および正規文法も、すべて正規言語の有限表現です。それらのすべての目的は、通常のセット/言語を表現することです (同じことが cfg や csl などの他のクラスの言語にも当てはまります)。

オートマトンは、言語特性を分析するための理論的な目的、つまり複雑さのクラスに比較的役立ちます。

有限オートマトンの場合、決定論的(DFA)モデルと非決定論的(NFA)モデルの両方が、「正規言語」と呼ばれる同じクラスの言語を表します (これは、npda ≭ pda の他の言語には当てはまりません)。

正規表現 (re): 正規言語をアルファベット形式で表すもう 1 つの方法です。これは、プログラミング言語で有効な文字列のセットを表すのに非常に役立ちます (ここでは、オートマトンは直接役に立ちませんが、正規表現は分析にはあまり役立ちません)。言語プロパティ (例: ポンピング補題を完全に記述するため)。

DFA と NFA は正規表現とどのように関連していますか?

  • どちらも同じクラスの言語を表します — 通常の言語

  • 英語の言語記述からアルゴリズム的にオートマトンや正規表現を直接構築することはできません。ただし、1 つの表現 (FA または RE) がある場合、他の表現を体系的に書くことができます。Arden の定理を使用して、DFA/NFA の正規表現を段階的かつ体系的に書くことができます。 （このリンクを確認してください）

    言語の例を見てみましょう: L = " a's とb's の偶数".

    L の正規表現は次のとおりです。

    (
 (a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a +
 (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b
)*

    この言語の正規表現を直接記述するのは非常に困難です (これをすぐに理解するのは少し典型的です)。

    しかし、DFA とアーデンの定理を使用すると、言語 L の正規表現を書くのは簡単でした。

    重要なのは、この言語の DFA の描画が比較的簡単である (覚えやすい) ことです。

    もう1つの例は、 「シンボル0と1、バイナリ文字列に相当する10進数が5で割り切れる」という言語である可能性があります。これに対してREを書くことは、DFAを書くことに比べて非常に困難です。

  • 正規言語からアルゴリズム的に DFA を引き出すこともできます。

DFA と NFA を学ぶことは、正規表現をよりよく理解するのに役立ちますか?

はい、次の理由によります。

  • RE を直接書くのは難しい場合があります。

  • 英語の記述から直接書かれた正規表現はバグがある可能性があります。バグのある dfa の可能性はバグのある正規表現よりも少ないため、ある言語のコンパイラを作成する場合、各トークンから最初に DFA を引き出し、次に同等の正規表現を作成することが望ましい/正しい手順と見なされます — DFA は正しさの証明と見なされます - dfaより記述的で理解しやすい言語構成 (DFA が正しい場合は RE が正しい)。

  • re が複雑で、「言語記述は何か」を調べたい場合は、re から DFA を引き出して言語記述を与えることができます。

  • より良いreを見つけるために、DFA を描画し、それを変換して DFA を最小化し、最小化された DFA を使用して re を記述すると、より良い解決策が得られる場合があります。（一般的なテクニックではないので、いつか役に立つかもしれません）

  • 2 つの正規表現を比較するのが難しい場合は、対応する DFA を比較して等価性を確認できます。

注: 正規表現を記述する方が、DFA を描画するよりもはるかに簡単な場合があります。

于 2013-07-07T13:48:14.777 に答える
0

非決定性有限オートマトン (NFA)は、通常の言語を認識できるマシンです。

正規表現は、正規言語を記述する文字列です。

特定の正規表現で記述された言語を認識する NFA をアルゴリズムで構築することができます。入力文字列に対して NFA を実行すると、正規表現が入力文字列と一致するかどうかがわかります。

そのため、NFA を使用して正規表現エンジンを実装できますが、正規表現を最大限に活用するために NFA の知識は必要ありません。

于 2013-07-07T07:36:26.917 に答える