☰

{0,1}에서 이러한 대칭 표현식을 egrep하는 것이 가능합니까?

tag-icon • tag-icon grep
{0,1}에서 이러한 대칭 표현식을 egrep하는 것이 가능합니까?

목표는 egrep을 사용하여 다음과 같은 표현식을 일치시키는 것입니다.N0 바로 뒤에 나타납니다.N1이 나타나고 1 뒤에 0이 없습니다.

예를 들어

01
000111
000000111111

하지만:

001
011
00011

등.

직관적으로 일치할 수 있는 표현식의 길이가 고정되어 있지 않기 때문에 이는 불가능해 보입니다. 하지만 아마도 이 작업에 유용할 수 있는 egrep 기능이 누락된 것일까요?

답변1

일부 CS 개념에 대한 간략한 개요:

  • 오토마타"언어"에 속하는 문자열을 허용합니다."문법"에 의해 생성되었습니다.
  • 정규 표현식은 (이론적으로) (결정적 또는 비결정적)과 동일합니다.유한 오토마타(DFA/NFA). 따라서 와 같은 정규 표현식이 있는 경우 0*1*DFA 및 NFA는 정규 표현식과 일치하는 문자열을 허용할 수 있습니다.
  • 유한 오토마타는 엄격하게 기능하지 않습니다.푸시다운 오토마톤(포켓 PC). PDA에서 허용하는 언어 범주는 다음에 의해 생성됩니다.문맥 자유 문법(CFG).
  • 보고 있는 문자열은 CFG에 의해 생성됩니다. (느슨하게 시작 문자열이 주어지면 원래 문자열의 양쪽에 문자열을 생성하거나 아무것도 생성하지 않을 수 있으므로 생성 등을 허용합니다.)0n1nS -> 0S1 | ε01010011

grep(확장 또는 기타)에는 위에서 언급한 역참조와 같은 "정규식" 이상의 기능이 있지만 이러한 기능 중 어떤 것도 PDA만큼 강력하도록 확장할 수는 없다고 생각합니다.

S -> 0S1 | ε다음을 사용하면 규칙적이지 않음을 알 수 있습니다.펌핑 보조정리, 그러나 grep의 기능이 CFG를 수용할 수 있는지(또는 수용할 수 없는지)에 대한 증거는 없습니다. 그러나 위키피디아 기사에는일반적인 표현이런 말이 있습니다(굵은 글씨는 내 것입니다).

거의 모든 최신 정규식 라이브러리에서 발견되는 많은 기능은 일반 언어보다 훨씬 강력한 표현력을 제공합니다. 예를 들어, 많은 구현에서는 괄호를 사용하여 하위 표현식을 그룹화하고 동일한 표현식(역참조)에서 일치하는 값을 호출할 수 있습니다. 이는 무엇보다도 패턴이 형식 언어 이론에서 사각형으로 알려진 "papa" 또는 "WikiWiki"와 같이 반복되는 단어 문자열과 일치할 수 있음을 의미합니다. 이 문자열의 패턴은 입니다 (.+)\1.

블록의 언어가 불규칙합니다.또한 컨텍스트 프리도 아닙니다., 펌프 보조정리로 인해. 그러나 무제한의 역참조를 사용한 패턴 일치는 많은 최신 도구에서 지원되는 것처럼 여전히 상황에 민감합니다. [33]

[33]: Cezar Câmpeanu, Kai Salomaa, Shen Yu(2003년 12월). "실용적인 정규식에 대한 공식적인 연구". 국제 컴퓨터 과학 기초 저널. 14(6):1007-1018. doi:10.1142/S012905410300214X. 정리 3(9페이지)

grep그러므로, 그 자체로는 일치하지 않을 것이라고 확실히 말할 수 있습니다 .0n1n

관련 정보