[regex] 둘러보기가 정규 표현식과 일치시킬 수있는 언어에 영향을 줍니까?

Program / 글쓴이

최신 정규식 엔진에는 해당 기능 없이는 일치시킬 수없는 언어를 일치시킬 수있는 몇 가지 기능이 있습니다. 예를 들어 역 참조를 사용하는 다음 정규식은 반복되는 단어로 구성된 모든 문자열의 언어와 일치합니다.(.+)\1 .. 이 언어는 규칙적이지 않으며 역 참조를 사용하지 않는 정규식과 일치시킬 수 없습니다.

둘러보기는 정규 표현식과 일치시킬 수있는 언어에도 영향을 미칩니 까? 즉, 그렇지 않으면 일치 할 수없는 lookaround를 사용하여 일치시킬 수있는 언어가 있습니까? 그렇다면 모든 종류의 룩 어라운드 (부정적 또는 긍정적 인 룩어 헤드 또는 룩 비하인드)에 해당됩니까, 아니면 일부에만 해당됩니까?

답변

다른 답변에서 주장했듯이 둘러보기는 정규 표현식에 추가 기능을 추가하지 않습니다.

다음을 사용하여 이것을 보여줄 수 있다고 생각합니다.

Pebble 2-NFA 1 개 (이를 참조하는 문서의 소개 섹션 참조).

1-pebble 2NFA는 중첩 된 lookaheads를 처리하지 않지만, multi-pebble 2NFA의 변형을 사용할 수 있습니다 (아래 섹션 참조).

소개

2-NFA는 입력에서 왼쪽 또는 오른쪽으로 이동할 수있는 능력이있는 비 결정적 유한 오토 마톤입니다.

하나의 조약돌 기계는 기계가 입력 테이프에 조약돌을 놓고 (즉, 조약돌로 특정 입력 기호를 표시) 현재 입력 위치에 조약돌이 있는지 여부에 따라 다른 전환을 수행 할 수있는 곳입니다.

One Pebble 2-NFA는 일반 DFA와 동일한 힘을 가지고있는 것으로 알려져 있습니다.

비 중첩 미리보기

기본 아이디어는 다음과 같습니다.

2NFA를 사용하면 입력 테이프에서 앞뒤로 이동하여 역 추적 (또는 ‘전면 트랙’) 할 수 있습니다. 따라서 예견을 위해 예견 정규식에 대한 일치를 수행 한 다음 예견 식을 일치시킬 때 사용한 것을 역 추적 할 수 있습니다. 역 추적을 멈출 때를 정확히 알기 위해 우리는 조약돌을 사용합니다! 역 추적을 중지해야하는 지점을 표시하기 위해 미리보기를 위해 dfa에 들어가기 전에 조약돌을 떨어 뜨립니다.

따라서 조약돌 2NFA를 통해 문자열을 실행하는 마지막에, 우리는 미리보기 표현식과 일치하는지 여부를 알고 있으며 입력 왼쪽 (즉, 소비 될 남은 것)이 나머지와 일치하는 데 필요한 것이 정확히 무엇인지 압니다.

따라서 u (? = v) w 형식의 예견을 위해

u, v 및 w에 대한 DFA가 있습니다.

u에 대한 DFA의 수락 상태 (예, 하나만 있다고 가정 할 수 있음)에서 입력을 조약돌로 표시하여 시작 상태 v로 전자 전환합니다.

v에 대한 수락 상태에서 조약돌을 찾을 때까지 입력을 계속 왼쪽으로 이동하는 상태로 전자 전환 한 다음 w의 시작 상태로 전환합니다.

거부 상태 v에서 우리는 조약돌을 찾을 때까지 계속 왼쪽으로 이동하는 상태로 전자 전환하고 u의 허용 상태 (즉, 중단 한 위치)로 전환합니다.

일반 NFA가 r1을 표시하는 데 사용되는 증명 | r2 또는 r * 등은이 하나의 조약돌 2nfa에 대해 이월됩니다. 더 큰 시스템을 제공하기 위해 구성 요소 시스템을 조합하는 방법에 대한 자세한 내용은 http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa 를 참조하십시오 . r * 표현식 등

위의 r * 등 증명이 작동하는 이유는 반복을 위해 구성 요소 nfas를 입력 할 때 입력 포인터가 항상 올바른 지점에 있도록 역 추적을 수행하기 때문입니다. 또한 조약돌이 사용 중이면 미리보기 구성 요소 시스템 중 하나에서 처리 중입니다. 완전히 역 추적하고 조약돌을 되찾지 않고는 예견 기계에서 예견 기계로의 전환이 없기 때문에 하나의 조약돌 기계 만 있으면됩니다.

예를 들어 ([^ a] | a (? = … b)) *

그리고 문자열 abbb.

a (? = … b)에 대한 peb2nfa를 통과하는 abbb가 있으며, 그 끝에는 상태 : (bbb, matched) (즉, 입력 bbb가 남아 있고 ‘a’와 일치했습니다. 뒤에 ‘..b’). 이제 * 때문에 처음으로 돌아가서 (위 링크의 구성 참조) [^ a]에 dfa를 입력합니다. b를 일치시키고 처음으로 돌아가서 [^ a]를 다시 두 번 입력 한 다음 수락합니다.

중첩 된 Lookahead 처리

중첩 된 미리보기를 처리하기 위해 여기에 정의 된대로 제한된 버전의 k-pebble 2NFA를 사용할 수 있습니다. 양방향 및 다중 페블 오토마타와 그 논리에 대한 복잡성 결과 (정의 4.1 정리 4.2 참조).

일반적으로 2 개의 pebble automata는 비정규 세트를 수용 할 수 있지만, 다음과 같은 제한 사항으로 인해 k-pebble automata는 규칙적인 것으로 표시 될 수 있습니다 (위 논문의 Theorem 4.2).

자갈이 P_1, P_2, …, P_K 인 경우

  • P_i가 이미 테이프에 있지 않으면 P_ {i + 1}을 배치 할 수없고 P_ {i + 1}이 테이프에 없으면 P_ {i}를 선택할 수 없습니다. 기본적으로 자갈은 LIFO 방식으로 사용되어야합니다.

  • P_ {i + 1}이 배치 된 시간과 P_ {i}가 선택되거나 P_ {i + 2}가 배치되는 시간 사이에 오토마타는 P_ {i}의 현재 위치 사이에있는 하위 단어 만 횡단 할 수 있습니다. 그리고 P_ {i + 1} 방향에있는 입력 단어의 끝. 또한이 하위 단어에서 오토 마톤은 Pebble P_ {i + 1}과 함께 1 조약돌 오토 마톤으로 만 작동 할 수 있습니다. 특히 다른 조약돌의 존재를 들어올 리거나 배치하거나 감지 할 수 없습니다.

따라서 v가 깊이 k의 중첩 된 미리보기 표현식이면 (? = v)는 ​​깊이 k + 1의 중첩 된 미리보기 표현식입니다. 내부 예견 기계에 들어가면 지금까지 얼마나 많은 조약돌을 놓아야하는지 정확히 알고 있으므로 어떤 조약돌을 놓을 지 정확하게 결정할 수 있고 그 기계에서 나올 때 어떤 조약돌을 들어 올릴 것인지 알 수 있습니다. 깊이 t에있는 모든 기계는 조약돌 t를 배치하여 들어가고 조약돌 t를 제거하여 나갑니다 (즉, 깊이 t-1 기계의 처리로 돌아갑니다). 전체 머신의 모든 실행은 트리의 재귀 dfs 호출처럼 보이며 위의 두 가지 제한 사항을 충족 할 수 있습니다.

이제 표현식을 결합 할 때 rr1에 대해 연결하므로 r1의 조약돌 수는 r의 깊이만큼 증가해야합니다. r * 및 r | r1의 경우 조약돌 번호는 동일하게 유지됩니다.

따라서 미리보기가있는 모든 표현은 조약돌 배치에 위의 제한 사항이있는 동등한 다중 조약돌 기계로 변환 될 수 있으므로 규칙적입니다.

결론

이것은 기본적으로 Francis의 원래 증명의 단점을 해결합니다. 예견 표현이 향후 경기에 필요한 모든 것을 소비하는 것을 방지 할 수 있다는 것입니다.

Lookbehind는 유한 문자열 (정규식이 아님) 일 뿐이므로 먼저 처리 한 다음 미리보기를 처리 할 수 ​​있습니다.

불완전한 글을 써서 미안하지만 완전한 증거에는 많은 그림을 그리는 것이 포함됩니다.

나에게는 옳게 보이지만 실수를 알고 있으면 기쁠 것입니다 (내가 좋아하는 것 같습니다 :-)).

답변

정규 언어보다 더 큰 언어 클래스를 둘러보기에 의해 확장 된 정규 표현식으로 인식 할 수 있는지 묻는 질문에 대한 대답은 ‘아니요’입니다.

증명은 비교적 간단하지만 둘러보기를 포함하는 정규식을없는 것으로 변환하는 알고리즘은 지저분합니다.

첫째 : 유한 알파벳을 통해 정규 표현식을 항상 부정 할 수 있습니다. 표현식에 의해 생성 된 언어를 인식하는 유한 상태 오토 마톤이 주어지면 모든 허용 상태를 비 수락 상태로 간단히 교환하여 해당 언어의 부정을 정확히 인식하는 FSA를 얻을 수 있습니다. 이에 상응하는 정규 표현식 제품군이 있습니다. .

둘째 : 정규 언어 (및 정규 표현식)가 부정으로 닫히기 때문에 A가 드 모건의 법칙에 따라 B = neg (neg (A) union neg (B))를 교차하므로 교차로에서도 닫힙니다. 즉, 두 개의 정규식이 주어지면 둘 다 일치하는 다른 정규식을 찾을 수 있습니다.

이를 통해 둘러보기 표현식을 시뮬레이션 할 수 있습니다. 예를 들어 u (? = v) w는 uv 및 uw와 일치하는 표현식 만 일치합니다.

부정 예견의 경우 집합 이론 A \ B에 해당하는 정규식이 필요합니다. 즉, A는 교차 (neg B) 또는 동등하게 neg (neg (A) union B)입니다. 따라서 정규식 r 및 s에 대해 s와 일치하지 않는 r과 일치하는 표현식과 일치하는 정규식 rs를 찾을 수 있습니다. 부정적 예측 용어로 : u (?! v) w는 uw-uv와 일치하는 표현식 만 일치합니다.

둘러보기가 유용한 이유는 두 가지입니다.

첫째, 정규 표현식의 부정은 훨씬 덜 깔끔한 결과를 가져올 수 있기 때문입니다. 예를 들면q(?!u)=q($|[^u]) .

둘째, 정규식은 일치 식 이상의 기능을 수행하며 문자열에서 문자를 소비합니다. 또는 적어도 우리가 생각하는 방식입니다. 예를 들어 파이썬에서는 .start () 및 .end ()에 대해 신경을 쓰고 있습니다.

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

셋째, 이것이 매우 중요한 이유라고 생각합니다. 정규 표현식의 부정은 연결보다 잘 들어 맞지 않습니다. neg (a) neg (b)는 neg (ab)와 동일하지 않습니다. 즉, 찾은 컨텍스트에서 둘러보기를 번역 할 수 없습니다. 전체 문자열을 처리해야합니다. 나는 사람들이 작업하는 것을 불쾌하게 만들고 정규 표현식에 대한 사람들의 직관을 깨뜨린다고 생각합니다.

나는 당신의 이론적 질문에 대답하기를 바랍니다 (밤 늦게, 불분명하면 용서하십시오). 나는 이것이 실제적인 응용이 있다고 말한 해설자에 동의합니다. 매우 복잡한 웹 페이지를 긁어 모 으려고 할 때 매우 동일한 문제를 만났습니다.

편집하다

명확하지 않은 것에 대해 사과드립니다. 구조적 유도에 의해 정규식 + 둘러보기의 정규성 증명을 제공 할 수 있다고 믿지 않습니다. 제 u (?! v) w 예제는 그저 예이고 쉬운 예입니다. 그것에. 구조적 유도가 작동하지 않는 이유는 둘러보기가 비구 성적인 방식으로 작동하기 때문입니다. 위의 부정에 대해 제가 말씀 드렸던 요점입니다. 나는 어떤 직접적인 공식적인 증명이 복잡한 세부 사항을 많이 가질 것이라고 생각합니다. 나는 그것을 보여줄 쉬운 방법을 생각했지만 내 머리 꼭대기에서 하나를 생각할 수 없다.

Josh의 첫 번째 예제 사용을 설명 ^([^a]|(?=..b))*$하기 위해 모든 주가 다음을 수락하는 7 개 주 DFSA와 동일합니다.

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               |
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

상태 A에 대한 정규식은 다음과 같습니다.

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

즉, 둘러보기를 제거하여 얻을 정규식은 일반적으로 훨씬 길고 더 지저분해질 것입니다.

Josh의 의견에 응답하기 위해-그렇습니다. 동등성을 증명하는 가장 직접적인 방법은 FSA를 통하는 것입니다. 이것을 더 복잡하게 만드는 것은 FSA를 구성하는 일반적인 방법이 비 결정적 기계를 통한다는 것입니다. u | v를 두 기계로 엡실론으로 전환하여 u와 v를 위해 기계로 구성한 기계처럼 간단하게 u | v를 표현하기가 훨씬 쉽습니다. 물론 이것은 결정 론적 기계와 동일하지만 상태가 기하 급수적으로 폭발 할 위험이 있습니다. 부정은 결정 론적 기계를 통해 수행하는 것이 훨씬 쉽습니다.

일반적인 증명에는 두 기계의 데카르트 곱을 취하고 둘러보기를 삽입하려는 각 지점에서 유지하려는 상태를 선택하는 것이 포함됩니다. 위의 예는 내가 의미하는 바를 어느 정도 보여줍니다.

공사를 제공하지 않은 것에 대해 사과드립니다.

추가 편집 : 블로그 게시물
을 찾았 습니다. 둘러보기가 추가 된 정규 표현식에서 DFA를 생성하는 알고리즘을 설명하는 을 습니다. 저자가 “태그 된 엡실론 전환”으로 NFA-e의 아이디어를 명백한 방식으로 확장 한 다음 이러한 자동 장치를 DFA로 변환하는 방법을 설명하기 때문에 깔끔합니다.

그렇게하는 것이 방법이라고 생각했지만 누군가가 그것을 써서 기쁩니다. 그렇게 깔끔한 것을 생각해내는 것은 저를 넘어 섰습니다.

답변

나는 둘러보기가 정규적이라는 다른 게시물에 동의하지만 (정규 표현식에 기본 기능을 추가하지 않는다는 의미), 내가 본 다른 게시물보다 IMO가 더 간단하다는 주장이 있습니다.

DFA 구성을 제공하여 둘러보기가 규칙적임을 보여 드리겠습니다. 언어는이를 인식하는 DFA가있는 경우에만 일반 언어입니다. Perl은 실제로 내부적으로 DFA를 사용하지 않지만 (자세한 내용은이 문서 참조 : http://swtch.com/~rsc/regexp/regexp1.html ) 증명을 위해 DFA를 구성합니다.

정규 표현식을위한 DFA를 구성하는 전통적인 방법은 먼저 Thompson의 알고리즘을 사용하여 NFA를 구축하는 것입니다. 두 개의 정규식 조각 r1과가 주어지면 r2Thompson의 알고리즘은 정규식 의 연결 ( r1r2), 교대 ( r1|r2) 및 반복 ( r1*)에 대한 구성을 제공합니다 . 이를 통해 원래 정규 표현식을 인식하는 NFA를 비트별로 빌드 할 수 있습니다. 자세한 내용은 위의 문서를 참조하십시오.

긍정 및 부정 예견이 규칙적임을 보여주기 위해 정규식 u을 긍정 또는 부정 예견과 연결하는 구성을 제공합니다 . (?=v)또는 (?!v). 연결에만 특별한 처리가 필요합니다. 일반적인 교대 및 반복 구조는 잘 작동합니다.

구성은 u (? = v)와 u (?! v) 모두 다음과 같습니다.

http://imgur.com/ClQpz.png

즉,에 대한 기존 NFA의 모든 최종 상태를 u수락 상태 와 에 대한 NFA 모두 v에 연결하지만 다음과 같이 수정합니다. 함수 f(v)는 다음과 같이 정의됩니다.

  • 모든 수락 상태를 “수락 방지 상태”로 변경 aa(v)하는 NFA의 함수가 되자 v. 안티 수락 상태가 실패 할 경기를 일으키는 상태로 정의 된 경우 어떤 주어진 문자열이 상태에서 NFA의 끝을 통해 경로 s,해도를 통해 다른 경로 v에 대한 saccept를 상태로 종료된다.
  • 하자 loop(v)NFA의 함수가 될 수 v있는 상태가 동의에 자체 전환을 추가합니다. 즉, 경로가 수락 상태에 도달하면 해당 경로는 어떤 입력이 뒤 따르더라도 영원히 수락 상태를 유지할 수 있습니다.
  • 부정적인 예측의 경우 f(v) = aa(loop(v)).
  • 긍정적 인 예측의 경우 f(v) = aa(neg(v)).

이것이 작동하는 이유에 대한 직관적 인 예를 제공하기 위해 나는 (b|a(?:.b))+Francis의 증명에 대한 주석에서 제안한 정규식의 약간 단순화 된 버전 인 regex를 사용할 것입니다. 전통적인 Thompson 구조와 함께 내 구조를 사용하면 다음과 같이 끝납니다.

대체 텍스트

e들 엡실론 전환 (전환 모든 입력을 사용하지 않고 촬영 할 수있다)하고있는 상태가 함께 표시되어 안티 동의 X. 그래프의 왼쪽 절반에서 다음과 같은 표현을 볼 수 있습니다 (a|b)+. any a또는 b그래프를 수락 상태로 설정하지만 다시 시작할 수 있도록 시작 상태로 다시 전환 할 수도 있습니다. 그러나 일치 할 때마다 a그래프의 오른쪽 절반에 들어가며 “any”다음에 b.

기존 NFA에는 반 수락 상태가 없기 때문에 이는 기존 NFA가 아닙니다. 그러나 기존 NFA-> DFA 알고리즘을 사용하여이를 기존 DFA로 변환 할 수 있습니다. 알고리즘은 평소와 같이 작동합니다. 여기서 DFA 상태를 우리가있을 수있는 NFA 상태의 하위 집합에 해당하도록하여 NFA의 여러 실행을 시뮬레이션합니다. 한 가지 문제는 DFA 상태가 다음과 같은지 여부를 결정하는 규칙을 약간 강화한다는 것입니다. (최종) 상태를 수락할지 여부. 기존의 알고리즘에서 DFA 상태는 경우가 상태를 받아 들일 것입니다 어떤 NFA의 상태가 상태가 동의했다. 다음과 같은 경우에만 DFA 상태가 수락 상태임을 나타내도록 수정합니다.

  • = 1 NFA 상태는 수락 상태 이고

  • 0 NFA 상태는 반 수락 상태입니다.

이 알고리즘은 미리보기로 정규 표현식을 인식하는 DFA를 제공합니다. Ergo, 예견은 규칙적입니다. lookbehind에는 별도의 증명이 필요합니다.

답변

여기에 두 가지 질문이 있습니다.

  • “lookaround”를 통합하는 Regex 엔진이 그렇지 않은 Regex 엔진보다 더 강력합니까?
  • “lookaround”가 Chomsky Type 3-Regular 문법 에서 생성 된 것보다 더 복잡한 언어를 구문 분석 할 수있는 능력을 Regex 엔진에 부여 합니까?

실용적인 의미에서 첫 번째 질문에 대한 대답은 ‘예’입니다. Lookaround는이 기능을 사용하는 Regex 엔진에 기본적으로 그렇지 않은 엔진보다 더 많은 성능을 제공합니다. 이는 매칭 프로세스에 더 풍부한 “앵커”세트를 제공하기 때문입니다. Lookaround를 사용하면 전체 Regex를 가능한 앵커 포인트 (폭이 0 인 어설 션)로 정의 할 수 있습니다. 여기 에서이 기능의 강력한 기능에 대한 개요를 볼 수 있습니다 .

Lookaround는 강력하기는하지만 유형 3 문법에서 정한 이론적 한계를 넘어 Regex 엔진을 들어 올리지는 않습니다. 예를 들어, Lookaround가 장착 된 Regex 엔진을 사용하여 Context Free-Type 2 Grammar 를
기반으로하는 언어 를 안정적으로 구문 분석 할 수 없습니다. 정규식 엔진은 유한 상태 자동화 의 힘
으로 제한되며 이는 파싱 할 수있는 모든 언어의 표현력을 유형 3 문법 수준으로 근본적으로 제한합니다. Regex 엔진에 추가 된 “트릭”의 수에 관계없이 언어는 문맥 자유 문법을
항상 그 능력을 뛰어 넘을 것입니다. 구문 분석 자유-유형 2 문법은 재귀 언어 구조의 위치를 ​​”기억”하기 위해 푸시 다운 자동화가 필요합니다. 문법 규칙의 재귀 적 평가가 필요한 것은 Regex 엔진을 사용하여 구문 분석 할 수 없습니다.

요약하면 : Lookaround는 Regex 엔진에 몇 가지 실질적인 이점을 제공하지만 이론적 수준에서 “게임을 변경”하지는 않습니다.

편집하다

Type 3 (Regular)와 Type 2 (Context Free) 사이에 복잡한 문법이 있습니까?

대답은 ‘아니오’라고 생각합니다. 그 이유는 일반 언어를 설명하는 데 필요한 NFA / DFA의 크기에 이론적 인 제한이 없기 때문입니다. 임의로 커져서 사용 (또는 지정)하는 것이 비실용적 일 수 있습니다. 이것은 “둘러보기”와 같은 회피가 유용한 곳입니다. 이는 매우 크고 복잡한 NFA / DFA 사양으로 이어질 항목을 지정하는 간단한 메커니즘을 제공합니다. 그들은 정규 언어의 표현력을 증가시키지 않고 단지 그들을 더 실용적으로 지정합니다. 이 점을 이해하면 실용적인 의미에서 더 유용하게 만들기 위해 Regex 엔진에 추가 할 수있는 많은 “기능”이 있다는 것이 분명해집니다. 그러나 정규 언어의 한계를 넘어 설 수있는 것은 없습니다. .

Regular 언어와 Context Free 언어의 기본적인 차이점은 Regular 언어에는 재귀 요소가 포함되어 있지 않다는 것입니다. 재귀 언어를 평가하려면 재귀에있는 위치를 “기억”하는 푸시 다운 자동화가 필요합니다. NFA / DFA는 상태 정보를 스택하지 않으므로 재귀를 처리 할 수 ​​없습니다. 따라서 비재 귀적 언어 정의가 주어지면이를 설명하기위한 NFA / DFA (실용적인 정규식 표현 일 필요는 없음)가 있습니다.

답변