18

ここで、現代の正規表現は正規言語で表現できるものを超えているというコメントをいくつか見ました。これはどうしてですか？

最新の正規表現のどの機能が正規ではありませんか? 例は役に立ちます。

4

3 に答える 3

4

いくつかの例：

  • 正規表現はグループ化をサポートします。たとえば、Rubyの場合：/my (group)/.match("my group")[1]「グループ」を出力します。グループに何かを格納するには、有限オートマトンにはない外部ストレージが必要です。
  • 多くの言語（C＃など）はキャプチャをサポートしています。つまり、各一致はスタックにキャプチャされます。たとえば、パターン(?<MYGROUP>.)*は「。」の複数のキャプチャを実行できます。同じグループ内。
  • 上記のユーザーNullUserExceptionで指摘されているように、グループ化は逆参照に使用されます。逆参照には、プッシュダウンオートマトンの機能を備えた1つ以上の外部スタックが必要です（スタックに何かをプッシュし、後でそれをピークまたはポップできる必要があります。
  • 一部のエンジンでは、外部スタックを個別にプッシュおよびポップし、スタックが空かどうかを確認する可能性があります。.NETでは、実際に(?<MYGROUP>test)はスタックをプッシュし、スタックを(?<-MYGROUP>)ポップします。
  • .NETエンジンなどの一部のエンジンには、バランスの取れたグループ化の概念があります。つまり、外部スタックを同時にプッシュおよびポップすることができます。バランスの取れたグループ化構文は(?<FIRSTGROUP-LASTGROUP>)、LASTGROUPをポップし、FIRSTGROUPスタックのLASTGROUPインデックス以降のキャプチャをプッシュする構文です。これは実際には、有限オートマトンの能力を確実に超えている、無限にネストされた構造に一致させるために使用できます。

おそらく他の良い例が存在します:-)正規表現とバランスの取れたグループ化、したがって有限オートマトンよりも高次のオートマトンと組み合わせた外部スタックの実装の詳細のいくつかにさらに興味がある場合は、これについて2つの短い記事を書いたことがあります（http：/ /www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspxおよび http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx）。

とにかく-完成度かどうか-この余分なものが正規言語にもたらす力は素晴らしいと思います:-)

Br。モーテン

于 2010-09-30T06:46:31.797 に答える
3

決定論的または非決定論的な有限オートマトンは、正規表現で記述された正規言語のみを認識します。正規表現の定義は単純です。Sをアルファベットとします。その場合、空集合、空文字列、および S のすべての要素は( Sに対する)正規表現です。uとvを正規表現とします。この場合、 uとvの結合 ( u | v )、連結 ( uv )、および閉包 ( u *) は、 S上の正規表現です。. この定義は、通常の言語に簡単に拡張できます。他の表現は正規表現ではありません。指摘したように、いくつかの後方参照は一例です。正規言語と正規表現に関するウィキペディアのページは参考になります。

本質的に、特定の「正規表現」は、特定のタイプのオートマトンを構築して認識できないため、正規表現ではありません。たとえば、言語

{ a^ i b^ i : i <= 0 }

規則的ではありません。これは、受け入れるオートマトンには無限に多くの状態が必要になるためですが、通常の言語を受け入れるオートマトンには有限数の状態が必要です。

于 2010-09-30T06:23:04.883 に答える