Ruby や Perl のプログラマーが、完全に正規表現のみを使用して複雑なコードの課題を解決しているのを見てきました。Perl 正規表現の先読み機能と後読み機能により、他のほとんどの言語の正規表現実装よりも強力になります。私は彼らが実際にどれほど強力なのか疑問に思っていました。
Perl 正規表現がチューリング完全であることを証明または反証する簡単な方法はありますか?
16144 次
3 に答える
31
などのあらゆる種類の埋め込みコードを除外すると?{ }、コンテキストフリーのすべて、ましてやチューリング マシンをカバーしていない可能性があります。可能性はあるかもしれませんが、私の知る限り、実際に何らかの方法でそれを証明した人はいません。人々が Perl 正規表現を使用して特定のコンテキスト フリーの問題を解決しようとしてしばらくの間、まだ解決策を考え出していないことを考えると、それらはコンテキスト フリーではない可能性があります。
どの機能が単に便利で、実際に機能を追加するかについて、興味深い議論があります。たとえば、0 n *1*0 n (「任意の数のゼロの後に 1 が続き、その後に前と同じ数のゼロが続く」という表記法) のマッチングは、純粋な正規表現では実行できません。Pumping Lemma を使用して正規表現でこれができないことを証明できますが、単純で非公式な証明は、正規表現は任意の数のゼロを数えなければならず、正規表現は数えることができないということです。
ただし、後方参照は次のものと一致させることができます。
/(0*) 1 \1/x;
つまり、後方参照はより強力であり、単なる便利ではありません。他に何が私たちにもっと力を与えてくれるのでしょうか？
また、Perl6 の「パターン」(もはや正規表現のふりすらしていません) は、Perl5 の正規表現のように見えるように設計されています (したがって、あまり再学習する必要はありません)。自由。それらは実際には、字句スコープ内で言語が解析される方法を変更するために使用できるように設計されています。
于 2011-11-02T20:11:06.790 に答える
18
少なくとも 2 つの議論があります:チューリングの完全性と正規表現とPerl パターンは普遍的ですか? さらなる参照とともに。
(素人目には) 答えは「いいえ」であると思われますが、すべてを正しく理解しているかどうかはわかりません。
于 2011-11-02T15:47:26.393 に答える
6
Perl の正規表現には、次の 2 つのケースがあります。
- 埋め込みコード: もちろんチューリング完全です。
- 埋め込みコードなし: 常に停止するため、一般的なチューリング マシンではありません。
有限オートマトンはすべての正規言語を受け入れることができます。その入力は有限文字列でなければなりません。
[...] 決定論的有限オートマトン (DFA) (決定論的有限状態マシンとも呼ばれる) は、有限のシンボル文字列を受け入れる/拒否する有限状態マシンです [...]。
同じことがチューリングマシンにも当てはまります。正式な定義には入力さえありません。有限数の状態でエンコードする必要があります。
于 2011-12-17T09:51:28.107 に答える