모든 정규식이 중지됩니까?

일부 입력 문자열의 경우 일치 항목을 영원히 검색 할 정규식이 있습니까?모든 정규식이 중지됩니까?

2009-08-06 Tom Lehman

... 정규식이 주어진 입력에 대해 정지할지 여부를 결정하는 프로그램을 작성할 수 있습니까? –

보너스 마크 - 정규식 사용! –

물론, mmyers와 mgb - 정규식에 연결된 입력에 대해 이것을 실행하십시오. /.*/ - 일치는 중지됨을 나타내며, 일치하지 않으면 일치하지 않습니다. : P – Amber

유한 입력의 경우 정식 정규식이 중지되지 않습니다.

공식 정규 표현식은 Deterministic Finite Automata로 변환 할 수 있습니다. DFA는 입력을 한 번에 한 문자 씩 읽으며 입력이 끝나면 수락 상태이거나 수락되지 않은 상태가됩니다. 상태가 수락되면 입력은 정규 표현식과 일치합니다. 그렇지 않으면 그렇지 않습니다.

이제 대부분의 "정규 표현식"라이브러리는 역 참조와 같이 정규 표현식이 아닌 것을 지원합니다.이러한 기능을 사용하지 않고 유한 한 입력이있는 한 중단이 보장됩니다. 당신이하지 않는다면 ... 당신이 무엇을 사용하고 있는지에 따라 멈추지 않을 수도 있습니다. Perl은 임의의 코드를 삽입 할 수있게 해주 며 임의의 turing-machine 코드는 멈추지 않을 것입니다.

이제 입력이 무한대이면, 결코 멈추지 않는 사소한 정규 표현식을 찾을 수 있습니다. (예 : ".*").

출처

2009-08-06 20:48:46

+1 역 참조를 언급합니다. – Brian

유일한 단서 : 명확한 것이 아닌 결정 론적 유한 오토마타라고 불립니다. (아이러니하게도, 동등한) 비 결정론적인 유한 오토마타와 대조를 이룬다. – agorenst

@Agor : 내가 할 때 나는 그것을 증오한다. 나는 정확한 이름을 잘 알고 있지만 어떤 이유로는 항상 잘못된 이름을 입력합니다. :-( –

당신이 묘사하는 의미는 아닙니다. 많은 리소스를 차지하고 정규식 엔진을 종료시키는 매우 비효율적 인 정규 표현식을 사용할 수 있습니다. 이는 정지와 동일하지 않습니다.

나는이 게시물의 다른 의견 작성자들이 매우 똑똑히 지적했듯이 실제로 중단이 적용되지 않는다고 생각합니다. http://en.wikipedia.org/wiki/Halting_problem

출처

2009-08-06 20:32:33

가능한 모든 프로그램 _이 멈추는 지 여부를 알려주는 프로그램을 만드는 방법은 없습니다. 그러나 그것이 하위 집합에 대해서는 그렇게 할 수 없다는 것을 의미하지는 않습니다. 어쩌면 정규 표현식은 그러한 부분 집합 중 하나이지만, 나는 모른다. – hsribei

여기서 정지 문제를 언급하는 것은별로 유용하지 않습니다. RE 매칭에 사용되는 알고리즘은 특정 알고리즘입니다. 중단 문제에 대한 흥미로운 점은 모든 프로그램 입력 쌍에 대해이를 해결하는 것입니다. –

(와우! 똑같은 초!) –

this question에 따르면 모든 정규 표현식이 중지됩니다.

출처

2009-08-06 20:38:20 hsribei

상상하지 말아야 할 정규 표현식을 찾을 수 없습니다.

입력 크기가 유한합니다. 일치하는 정규 표현식의 하위 그룹의 최대 크기는 입력 한 크기의 최대 값입니다.

사용되는 알고리즘이 꽤 어리 석다면 (여러 번 소송을 거듭하는 경우), 일치하는 하위 그룹의 수 역시 제한적입니다.

따라서 중단됩니다.

출처

2009-08-06 20:38:35

무한히 긴 문자열이 영원히 파싱 되더라도 영원히 파싱 할 입력 문자열은 상상할 수 없습니다. 정규 표현식이 잠재적으로 무한한 단어 집합 인 정규 언어를 기술 할 수 있다고 가정하면 정규 표현식은 무한한 길이의 단어를 포함하여 무한한 단어의 언어를 기술 할 수 있습니다. 그러나 입력 문자열은 무한히 길 수 없으므로 어떤 시점에서는 중단해야합니다.

예를 들어, a * b가 언어에서 허용되고 'a'가 무한히 긴 문자열이면 예, 정규식이 중단되지 않습니다. 실제로, 이것은 불가능합니다.

출처

2009-08-06 20:41:45 bkritzer

공식 정규식은 실제로 문자열을 구문 분석하기위한 결정 론적 유한 오토 마톤을 설명하는 방법입니다. 정규 표현식은 DFA가 입력의 끝에서 수락 상태가 될 때 "일치"합니다. DFA는 입력을 순차적으로 읽으므로 입력이 끝나면 항상 중단되고 일치 여부는 DFA의 어느 상태가 중단되었는지를 검사하는 것일뿐입니다.

부분 문자열 일치는 사실상 동일하지만 문자열의 한 리드 스루 끝에서 중단되도록 강제하는 대신 DFA는 가능한 한 각 부분 문자열을 읽은 후에 강제 종료됩니다 (유한 한 경우). (예, 대다수의 정규식 엔진은 DFA에 가능한 모든 하위 문자열을 던지는 것보다 조금 더 최적화 된 방식으로이 기능을 구현하지만 개념적으로는 여전히 한계가 있습니다.)

따라서 DFA가 중단되지 않는 유일한 경우는 입력이 무한대 인 경우이며 일반적으로 중지 문제의 범위를 벗어난 것으로 간주됩니다.

출처

2009-08-06 20:46:27 Amber

예.

정규식은 유한 상태 시스템으로 나타낼 수 있습니다. 원자 입력을받을 때마다 잘 정의 된 FSM이 알려진 상태로 전환됩니다.

무한 입력이있는 경우는 예외이지만 유한 입력을 처리하기 때문에 중지 문제에는 적용 할 수 없습니다. 유한 상태 기계와 유한 입력이있는 경우 기계가 정지할지 여부를 항상 판별 할 수 있습니다. 다니엘의 답변

출처

2009-08-06 21:00:00 Unknown