[解決済み] 正規表現を使って回文であることを確認するには？

質問

インタビューでの質問で、答えられなかった。

正規表現を使って文字列が回文であることを確認する方法は？

p.s. 既に質問 " があります。 与えられた文字列が回文であるかどうかを確認するにはどうすればよいですか？ という質問があり、様々な言語で多くの回答がありますが、正規表現を使った回答はありません。

どのように解決するのですか？

この質問に対する答えは、「不可能だ」です。より具体的には、面接官はあなたが計算論の授業に注意を払ったかどうかを気にしているのです。

計算理論の授業では、有限状態機械について学びましたね。有限状態機械はノードとエッジで構成されています。各エッジは有限のアルファベットからの文字で注釈されています。1つ以上のノードは特別なノード（quot;accepting"）で、1つのノードはノード（quot;start"）である。各文字が与えられた単語から読まれるとき、我々は機械内の与えられたエッジをトラバースする。もし私たちがacceptingの状態で終わったら、マシンがその単語をquot;accepts"したと言うのです。

正規表現は常に等価な有限状態機械に翻訳することができます。つまり、正規表現と同じ単語を受け入れたり拒否したりするものです (現実世界では、いくつかの正規表現言語では任意の関数を使用できますが、これはカウントされません)。

すべての回文を受け入れる有限状態マシンを構築することは不可能です。この証明は、任意の数のノードを必要とする文字列を簡単に構築できるという事実に依存しており、すなわち、文字列

a^x b a^x (例: aba, aabaa, aaabaaa, aaaabaaa, ......)

ここで、a^xはx回繰り返されるものです。これは、「b」を見た後、回文であることを確認するために x 回数を数える必要があるため、少なくとも x 個のノードが必要です。

最後に、元の質問に戻りますが、ある有限の固定長より小さい回文をすべて受け入れる正規表現を書くことができると面接官に伝えることができます。回文を識別する必要がある現実のアプリケーションがあるとすれば、そのアプリケーションには任意に長い回文は含まれないでしょうから、この回答は、理論上の不可能性と現実のアプリケーションを区別できることを示すことになるでしょう。それでも、実際の正規表現はかなり長くなり、同等の 4 行プログラムよりもはるかに長くなります (読者のための簡単な練習: 回文を識別するプログラムを書いてみてください)。