☰

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

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

目標は、egrepを使用して次の式を一致させることです。N0の直後に表示されます。N1が表示され、1の後にゼロはありません。

例えば

01
000111
000000111111

しかし：

001
011
00011

など。

直感的に一致できる式の長さが固定されていないため、これは不可能に見えます。しかし、おそらくこの作業に役立つ可能性のあるegrep機能がありませんか？

答え1

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

  • オートマタ「言語」に属する文字列を受け入れます。「文法」によって作成されました。
  • 正規表現は（理論的に）（決定的または非決定的）と同じです。有限オートマタ（DFA/NFA）。したがって、などの正規表現がある場合、0*1*DFAとNFAは正規表現と一致する文字列を受け入れることができます。
  • 有限オートマトンは厳密には機能しません。プッシュダウンオートマトン（ポケットPC）。 PDA が許可する言語カテゴリは、次のように生成されます。文脈自由文法(CFG)。
  • 見ている文字列はCFGによって生成されます。 (緩やかに開始文字列が与えられると、元の文字列の両側に文字列を生成したり、何も生成しない可能性があるため、生成などを許可します.)0n1nS -> 0S1 | ε01010011

grep（拡張またはその他）には、上記の逆参照などの「正規表現」以上の機能がありますが、これらの機能のどれもPDAほど強力になるように拡張することはできないと思います。

S -> 0S1 | ε以下を使用すると、規則的ではないことがわかります。ポンピング補助整理しかし、grepの機能がCFGを受け入れることができるか（または受け入れられないか）という証拠はありません。しかし、ウィキペディアの記事では一般的な表現このような言葉があります（太字は私のものです）。

ほとんどすべての最新の正規表現ライブラリに見られる多くの機能は、一般言語よりはるかに強力な表現力を提供します。たとえば、多くの実装では、括弧を使用して子式をグループ化し、同じ式（逆参照）から一致する値を呼び出すことができます。これは、パターンがフォーマット言語理論の正方形として知られている「papa」や「WikiWiki」など、繰り返しの単語文字列と一致する可能性があることを意味します。この文字列のパターンはです(.+)\1。

ブロックの言語が不規則です。また、コンテキストフリーでもありません。、ポンプ補助整理のため。しかし、無制限の逆参照を使用したパターンマッチングは、多くの最新ツールでサポートされているように、依然として状況に敏感です。[33]

[33]：Cezar Câmpeanu、Kai Salomaa、Shen Yu（2003年12月）。 「実用的な正規表現の正式な研究」。国際コンピュータサイエンス基礎ジャーナル。 14(6):1007-1018。 doi:10.1142/S012905410300214X.まとめ3（9ページ）

grepしたがって、それ自体は一致しないと確かに言うことができます。0n1n

関連情報