[regex] 정규식을 사용하여 문자열이 회문인지 확인하는 방법은 무엇입니까?

이 질문에 대한 대답은 “불가능하다”는 것입니다. 더 구체적으로 면접관은 당신이 계산 이론 수업에 관심을 기울 였는지 궁금해합니다.

계산 이론 수업에서 유한 상태 기계에 대해 배웠습니다. 유한 상태 머신은 노드와 에지로 구성됩니다. 각 모서리에는 유한 알파벳의 문자가 주석으로 표시됩니다. 하나 이상의 노드는 특수한 “수락”노드이고 한 노드는 “시작”노드입니다. 주어진 단어에서 각 문자를 읽을 때 우리는 기계의 주어진 가장자리를 횡단합니다. 수락 상태가되면 기계가 해당 단어를 “수락”한다고 말합니다.

정규식은 항상 동등한 유한 상태 기계로 변환 될 수 있습니다. 즉, 정규 표현식과 동일한 단어를 허용하고 거부하는 것입니다 (실제 세계에서 일부 정규 표현식 언어는 임의의 함수를 허용하지만 계산되지 않음).

모든 회문을 받아들이는 유한 상태 기계를 만드는 것은 불가능합니다. 증명은 임의로 많은 수의 노드가 필요한 문자열, 즉 문자열을 쉽게 만들 수 있다는 사실에 의존합니다.

a ^ xba ^ x (예 : aba, aabaa, aaabaaa, aaaabaaaa, ….)

여기서 a ^ x는 x 번 반복됩니다. ‘b’를 본 후 회문인지 확인하기 위해 x 번 카운트해야하기 때문에 최소 x 개의 노드가 필요합니다.

마지막으로, 원래의 질문으로 돌아가서 면접관에게 유한 고정 길이보다 작은 모든 회문을 받아들이는 정규식을 작성할 수 있다고 말할 수 있습니다. 회문을 식별해야하는 실제 응용 프로그램이있는 경우 임의로 긴 응용 프로그램을 포함하지 않을 것이므로이 답변은 이론적 불가능 성을 실제 응용 프로그램과 구별 할 수 있음을 보여줍니다. 그래도 실제 정규 표현식은 동등한 4 줄 프로그램보다 훨씬 길다 (독자를위한 쉬운 연습 : 회문을 식별하는 프로그램 작성).

답변

$a = "teststring";
while(length $a > 1)
{
   $a =~ /(.)(.*)(.)/;
   die "Not a palindrome: $a" unless $1 eq $3;
   $a = $2;
}
print "Palindrome";

/^((.)(?1)\2|.?)$/

\(.\)\(.\)\2\1

\([a-z]\)\([a-z]\)[a-z]\2\1

(?<N>.)+.?(?<-N>\k<N>)+(?(N)(?!))