☰

{0,1}上のこれらの対称式をegrepすることは可能ですか？

tag-icon • tag-icon grep
{0,1}上のこれらの対称式をegrepすることは可能ですか？

目標は、egrepのみを使用して、ん0の出現の後にちょうどん1 の出現回数と、1 の後に 0 が続かない回数。

例えば

01
000111
000000111111

だがしかし：

001
011
00011

等

直感的には、一致可能な表現の長さが固定されていないため、これは実現できないように思えます。しかし、おそらく、これに役立つ egrep の機能を見逃しているのでしょうか?

答え1

いくつかの CS 概念の簡単な概要:

  • オートマタ「言語」に属する文字列を受け入れる、「文法」によって生成されます。
  • 正規表現は（理論上は）（決定論的または非決定論的）と同等である。有限オートマトン(DFA/NFA)。したがって、のような正規表現が与えられた場合0*1*、その正規表現に一致する文字列を受け入れることができる DFA と NFA が存在します。
  • 有限オートマトンは以下のものより厳密に劣るプッシュダウンオートマトン（PDA）。PDAが受け入れる言語のクラスは、文脈自由文法（CFG）。
  • あなたが見ている文字列 - - は、CFG によって生成されます: (大まかに言えば、開始文字列が与えられると、元の文字列の両側にとを含む文字列を生成することも、何も生成しないこともできます。つまり、 、 などを生成できます)。0n1nS -> 0S1 | ε01010011

grep (拡張版またはそれ以外) には、バック参照など、前述の「正規表現」を超える機能がありますが、それらのいずれもが PDA と同じくらい強力になるとは思いません。

S -> 0S1 | εが正規でないことは、ポンピングの補題、しかし、grepの機能によってCFGを受け入れることができる（または受け入れることができない）という証拠はありません。しかし、Wikipediaの記事では、正規表現こう言っています（太字は筆者によるものです）。

ほぼすべての最新の正規表現ライブラリに備わっている多くの機能は、正規言語をはるかに超える表現力を提供します。たとえば、多くの実装では、括弧を使用して部分式をグループ化し、同じ式内で一致する値を呼び出すことができます (後方参照)。つまり、パターンは、形式言語理論ではスクエアと呼ばれる「papa」や「WikiWiki」などの繰り返し単語の文字列に一致できます。これらの文字列のパターンは です(.+)\1。

正方形の言語は規則的ではない。文脈に依存しない、ポンピング補題により、これは成り立つ。しかし、多くの現代のツールでサポートされているように、無制限の数のバックリファレンスによるパターンマッチングは、依然として文脈に依存している。[33]

[33]: Cezar Câmpeanu、Kai Salomaa、Sheng Yu (2003年12月)。「実用的な正規表現の形式的研究」。International Journal of Foundations of Computer Science。14 (6): 1007–1018。doi:10.1142/S012905410300214X。定理3 (p.9)

grepしたがって、それだけでは一致しないと言っても過言ではないでしょう。0n1n

関連情報