関連する質問/資料:
数値が正規表現で素数かどうかを判断する方法は? （単項素数マッチングを扱いますが、基数≧2を探していますが、それでも良いトリックであり、これについて考えさせられた理由）
http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html
よく知られているように、さまざまなプログラミング言語でサポートされている「正規表現」は、形式的な意味で非正規の言語を生成し、上記の資料で示されているように、少なくともいくつかの文脈依存言語を認識できます。
言語 L = {x | x は基数 10 の素数です。} は、素数性が線形有界オートマトンによってテストできるため、文脈依存言語です (ただし、ポンピング レンマ引数による文脈自由言語ではありません)。
では、基数 10 のすべての素数を正確に受け入れる Perl または Java の正規表現を作成することは可能でしょうか? 2 以上の他の基数に置き換えるか、すべての合成数を正確に認識する方が簡単だと思われる場合は、自由に置き換えてください。
たとえば、エスケープを使用して任意の Perl コードを実行することは、不正行為と見なされます。置換を繰り返し行うこと (簡単にチューリング完全になる) も範囲外です。全体の作業は正規表現内で行う必要があります。この質問は、正規表現が実際にどれほど強力であるかの境界に関するものです。