목표는 egrep만을 사용하여 표현식을 일치시키는 것입니다.N0이 발생하면 정확히 다음과 같습니다.N1이 발생하고 1 다음에 0이 나오지 않습니다.
예를 들어
01
000111
000000111111
하지만:
001
011
00011
등.
직관적으로 이것은 일치하는 표현식이 고정된 길이가 아니기 때문에 달성할 수 없는 것 같습니다. 하지만 아마도 이것에 유용할 수 있는 egrep 기능이 누락된 것일까요?
답변1
일부 CS 개념에 대한 간략한 개요:
- 오토마타"언어"에 속하는 문자열을 허용합니다."문법"에 의해 생성됩니다.
- (이론적으로) 정규식은 (결정적 또는 비결정적)과 동일합니다.유한 오토마타(DFA/NFA). 따라서 와 같은 정규식이 주어지면
0*1*해당 정규식과 일치하는 문자열을 허용할 수 있는 DFA 및 NFA가 있습니다. - 유한 오토마타는 다음보다 강력하지 않습니다.푸시다운 오토마타(PDA). PDA가 허용하는 언어 클래스는 다음에 의해 생성됩니다.문맥 자유 문법(CFG).
- 보고 있는 문자열은 CFG에 의해 생성됩니다. (느슨하게 시작 문자열이 주어지면 원래 문자열의 양쪽에 문자열을 생성하거나 아무것도 생성하지 않을 수 있습니다 . 따라서 , 등을 생성할 수 있습니다. ).
0n1nS -> 0S1 | ε01010011
grep(확장 또는 기타)에는 위에서 언급한 역참조와 같은 "정규식" 이상의 기능이 있지만 그 중 어느 것도 PDA만큼 강력하게 확장할 수는 없다고 생각합니다.
S -> 0S1 | ε다음을 사용하여 규칙적이지 않음 을 증명할 수 있습니다.펌핑 보조정리, 그러나 grep의 기능이 CFG를 허용(또는 불가능)하게 만드는 증거가 없습니다. 그러나 Wikipedia 기사에는정규 표현식이런 말이 있습니다(굵은 글씨):
거의 모든 최신 정규식 라이브러리에서 발견되는 많은 기능은 일반 언어를 훨씬 능가하는 표현력을 제공합니다. 예를 들어, 많은 구현에서는 하위 표현식을 괄호로 그룹화하고 동일한 표현식(역참조)에서 일치하는 값을 호출할 수 있습니다. 이는 무엇보다도 패턴이 형식 언어 이론에서 사각형이라고 불리는 "papa" 또는 "WikiWiki"와 같은 반복 단어 문자열과 일치할 수 있음을 의미합니다. 이 문자열의 패턴은 입니다
(.+)\1.사각형의 언어는 규칙적이지 않습니다.또한 맥락에 무관하지도 않습니다., 펌핑 보조정리로 인해. 그러나 수많은 최신 도구에서 지원되는 무제한의 역참조를 사용한 패턴 일치는 여전히 상황에 민감합니다. [33]
[33]: Cezar Câmpeanu, Kai Salomaa, Sheng Yu(2003년 12월). "실용적인 정규 표현식에 대한 공식적인 연구". 컴퓨터 과학 기초 국제 저널. 14 (6): 1007-1018. doi:10.1142/S012905410300214X. 정리 3 (p.9)
grep따라서 그 자체로는 일치할 수 없다고 말하는 것이 안전하다고 말하고 싶습니다 .0n1n