12

正規表現は、完全ではない言語の古典的な例としてしばしば指摘されます。たとえば、チューリング完全ではない言語を探すこのSOの質問に対する答えとして、「正規表現」が示されています。

ターニングの完全性の概念についての私の、おそらくある程度基本的な理解では、これは、「バランスの取れた」パターンをチェックするために正規表現を使用できないことを意味します。バランスの取れた意味には、終了文字と同じ数の開始文字があります。これを行うには、開始文字と終了文字を一致させるために、何らかの状態が必要になるためです。

ただし、正規表現の.NET実装では、バランスの取れたグループの概念が導入されています。この構成は、前のグループが一致したかどうかをさかのぼって確認できるように設計されています。これは、.NET正規表現が次のことを意味します。

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

次のようなパターンに一致する可能性があります。

ab
aabb
aaabbb
aaaabbbb
... etc. ...

これは、.NETの正規表現がチューリング完全であることを意味しますか？または、言語をチューリング完全にするために必要な、不足している他のものはありますか？

4

4 に答える 4

6

計算理論では、正規表現は正規言語を表します。正規言語のクラスは、正確には、有限状態マシンによって認識されるか、正規文法によって生成される言語です。ただし、説明した例（バランスの取れたフレーズ）は正規言語ではなく、有限状態マシンで認識したり、正規文法で生成したりすることはできません。実際、これはいわゆる文脈自由言語の教科書の例です。これらは、認識のためにプッシュダウンオートマトンを必要とします。文脈自由言語のクラスは、正規言語のスーパーセットですが、チューリング完全言語の適切なサブセットです。ほとんどのプログラミング言語の構文（セマンティクスではなく）は、文脈自由言語です。このトピックについて詳しく知りたい場合は、チョムスキー階層

于 2011-01-31T04:53:11.413 に答える
5

.NET の正規表現は常に停止するため、完全なチューリングではありません。これは一般的なチューリングマシンとは言えません。

于 2011-12-17T09:50:14.003 に答える
4

完全なチューリングの定義をほとんど見逃しています。

アラン チューリングにちなんで名付けられたチューリングの完全性は、これまでに進歩したコンピューティング デバイスのすべての妥当な設計がユニバーサル チューリング マシンによってエミュレートできるという点で重要です。したがって、万能チューリングマシンとして機能できるマシンは、原則として、他のプログラム可能なコンピューターが実行できるあらゆる計算を実行できます。ただし、これは、マシンのプログラムを作成するために必要な労力、マシンが計算を実行するのにかかる時間、またはマシンが持つ計算とは関係のない能力とは何の関係もありません。

現在、正規表現では特定のことを行うことができないため、言語は完全にはチューリングされていません。

他の人と同じ定義を使用する必要があります。限られた理解は、真実を発見するきっかけとなるはずです。

于 2011-01-29T07:17:58.233 に答える
3

@犬夜叉：実は正規表現で足し算ができます。少なくとも、計算が正しく行われたかどうかを確認してください。唯一のことは、正規表現への入力を奇妙な順序で指定する必要があることです（正規表現を使用して文字列を逆にする（または逆になっているかどうかを確認する）ことはできません）。

パターンは次のとおりです。

abc
def
---
ghi

=> cfi beh adg

1011と0110をバイナリで追加するとします。

01011
00110
-----
10001


=> 101 110 010 100 001

この入力をリースの有効ビットから最大の順に指定し、第1オペランド、第2オペランド、および出力を散在させると、文字列101110010100001が得られます。これは次のように一致します。

((000|011|101)|(110(010|100|111)*001))*

これは庭の品種の正規表現です。これを10進数の加算に拡張することもできますが、正規表現は非常に複雑になります。

于 2011-03-16T03:57:05.923 に答える