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

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

---

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

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

---

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

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

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

1-pebble 2NFA는 중첩 된 lookahead를 처리하지 않지만, 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를 기계로 구성한 기계처럼 간단하게 표현하기가 훨씬 쉽습니다. 물론 이것은 결정 론적 기계와 동일하지만 상태가 기하 급수적으로 폭발 할 위험이 있습니다. 부정은 결정 론적 기계를 통해 훨씬 쉽게 할 수 있습니다.

The general proof will involve taking the cartesian product of two machines and selecting those states you wish to retain at each point you want to insert a lookaround. The example above illustrates what I mean to some extent.

My apologies for not supplying a construction.

FURTHER EDIT: I have found a blog post which describes an algorithm for generating a DFA out of a regular expression augmented with lookarounds. Its neat because the author extends the idea of an NFA-e with "tagged epsilon transitions" in the obvious way, and then explains how to convert such an automaton into a DFA.

I thought something like that would be a way to do it, but I'm pleased that someone has written it up. It was beyond me to come up with something so neat.

---

I agree with the other posts that lookaround is regular (meaning that it does not add any fundamental capability to regular expressions), but I have an argument for it that is simpler IMO than the other ones I have seen.

I will show that lookaround is regular by providing a DFA construction. A language is regular if and only if it has a DFA that recognizes it. Note that Perl doesn't actually use DFAs internally (see this paper for details: http://swtch.com/~rsc/regexp/regexp1.html) but we construct a DFA for purposes of the proof.

The traditional way of constructing a DFA for a regular expression is to first build an NFA using Thompson's Algorithm. Given two regular expressions fragments r1 and r2, Thompson's Algorithm provides constructions for concatenation (r1r2), alternation (r1|r2), and repetition (r1*) of regular expressions. This allows you to build a NFA bit by bit that recognizes the original regular expression. See the paper above for more details.

To show that positive and negative lookahead are regular, I will provide a construction for concatenation of a regular expression u with positive or negative lookahead: (?=v) or (?!v). Only concatenation requires special treatment; the usual alternation and repetition constructions work fine.

The construction is for both u(?=v) and u(?!v) is:

In other words, connect every final state of the existing NFA for u to both an accept state and to an NFA for v, but modified as follows. The function f(v) is defined as:

• Let aa(v) be a function on an NFA v that changes every accept state into an "anti-accept state". An anti-accept state is defined to be a state that causes the match to fail if any path through the NFA ends in this state for a given string s, even if a different path through v for s ends in an accept state.
• Let loop(v) be a function on an NFA v that adds a self-transition on any accept state. In other words, once a path leads to an accept state, that path can stay in the accept state forever no matter what input follows.
• For negative lookahead, f(v) = aa(loop(v)).
• For positive lookahead, f(v) = aa(neg(v)).

To provide an intuitive example for why this works, I will use the regex (b|a(?:.b))+, which is a slightly simplified version of the regex I proposed in the comments of Francis's proof. If we use my construction along with the traditional Thompson constructions, we end up with:

The es are epsilon transitions (transitions that can be taken without consuming any input) and the anti-accept states are labeled with an X. In the left half of the graph you see the representation of (a|b)+: any a or b puts the graph in an accept state, but also allows a transition back to the begin state so we can do it again. But note that every time we match an a we also enter the right half of the graph, where we are in anti-accept states until we match "any" followed by a b.

This is not a traditional NFA because traditional NFAs don't have anti-accept states. However we can use the traditional NFA->DFA algorithm to convert this into a traditional DFA. The algorithm works like usual, where we simulate multiple runs of the NFA by making our DFA states correspond to subsets of the NFA states we could possibly be in. The one twist is that we slightly augment the rule for deciding if a DFA state is an accept (final) state or not. In the traditional algorithm a DFA state is an accept state if any of the NFA states was an accept state. We modify this to say that a DFA state is an accept state if and only if:

• = 1 NFA states is an accept state, and

• 0 NFA states are anti-accept states.

This algorithm will give us a DFA that recognizes the regular expression with lookahead. Ergo, lookahead is regular. Note that lookbehind requires a separate proof.

---

I have a feeling that there are two distinct questions being asked here:

• Are Regex engines that encorporate "lookaround" more powerful than Regex engines that don't?
• Does "lookaround" empower a Regex engine with the ability to parse languages that are more complex than those generated from a Chomsky Type 3 - Regular grammar?

The answer to the first question in a practical sense is yes. Lookaround will give a Regex engine that uses this feature fundamentally more power than one that doesn't. This is because it provides a richer set of "anchors" for the matching process. Lookaround lets you define an entire Regex as a possible anchor point (zero width assertion). You can get a pretty good overview of the power of this feature here.

Lookaround, although powerful, does not lift the Regex engine beyond the theoretical limits placed on it by a Type 3 Grammar. For example, you will never be able to reliably parse a language based on a Context Free - Type 2 Grammar using a Regex engine equipped with lookaround. Regex engines are limited to the power of a Finite State Automation and this fundamentally restricts the expressiveness of any language they can parse to the level of a Type 3 Grammar. No matter how many "tricks" are added to your Regex engine, languages generated via a Context Free Grammar will always remain beyond its capabilities. Parsing Context Free - Type 2 grammar requires pushdown automation to "remember" where it is in a recursive language construct. Anything that requires a recursive evaluation of the grammar rules cannot be parsed using Regex engines.

To summarize: Lookaround provides some practical benefits to Regex engines but does not "alter the game" on a theoretical level.

EDIT

Is there some grammar with a complexity somewhere between Type 3 (Regular) and Type 2 (Context Free)?

I believe the answer is no. The reason is because there is no theoretical limit placed on the size of the NFA/DFA needed to describe a Regular language. It may become arbitrarily large and therefore impractical to use (or specify). This is where dodges such as "lookaround" are useful. They provide a short-hand mechanism to specify what would otherwise lead to very large/complex NFA/DFA specifications. They do not increase the expressiveness of Regular languages, they just make specifying them more practical. Once you get this point, it becomes clear that there are a lot of "features" that could be added to Regex engines to make them more useful in a practical sense - but nothing will make them capable of going beyond the limits of a Regular language.

The basic difference between a Regular and a Context Free language is that a Regular language does not contain recursive elements. In order to evaluate a recursive language you need a Push Down Automation to "remember" where you are in the recursion. An NFA/DFA does not stack state information so cannot handle the recursion. So given a non-recursive language definition there will be some NFA/DFA (but not necessarily a practical Regex expression) to describe it.

참고URL : https://stackoverflow.com/questions/2974210/does-lookaround-affect-which-languages-can-be-matched-by-regular-expressions