펌핑 속성이 유지되기 위해 충족해야 하는 조건은 무엇입니까?

/ / 에 게시됨 사이버 보안, EITC/IS/CCTF 계산 복잡도 이론 기초, 상황에 맞는 언어, CFL을위한 펌핑 기본형, 심사 검토

펌핑 보조정리라고도 하는 펌핑 속성은 계산 복잡도 이론 분야, 특히 상황에 맞는 언어(CSL) 연구에서 기본 개념입니다. 펌핑 속성은 언어가 상황에 따라 달라지는 데 필요한 조건을 제공하며 특정 언어가 상황에 따라 달라지지 않음을 증명하는 데 도움이 됩니다.

펌핑 속성이 유지되기 위해 충족해야 하는 조건을 이해하기 위해 먼저 상황에 맞는 언어가 무엇인지 정의해 보겠습니다. 상황에 맞는 언어는 생산 규칙이 생성되는 문자열의 컨텍스트를 수정할 수 있도록 허용되는 형식 문법의 한 유형인 상황에 맞는 문법에 의해 생성될 수 있는 형식 언어입니다. 즉, 문법은 인식을 위해 어떤 형태의 컨텍스트가 필요한 언어를 인식하고 생성할 수 있습니다.

CSL의 펌핑 보조정리라고도 하는 상황에 맞는 언어의 펌핑 속성은 언어 L이 상황에 맞는 경우 상수 p(펌핑 길이)가 존재하여 L의 충분히 긴 문자열 w가 다음 조건을 만족하는 XNUMX개 부분: uvxyz로 나누어야 합니다.

1. 결합된 v와 y의 길이가 0보다 큽니다. 즉, |vxy| > XNUMX.
2. uvxy의 길이는 기껏해야 p, 즉 |uvxy| ≤ p.
3. 음수가 아닌 정수 k의 경우 문자열 uv^kxy^kz도 L에 있습니다.

이러한 조건을 명확히 하기 위해 예를 들어 보겠습니다. 언어 L = {a^nb^nc^n | n ≥ 0}, 같은 수의 'a', 'b', 'c' 순서로 구성된 문자열 집합을 나타냅니다. 이 언어가 펌핑 속성을 충족하는지 확인하려고 합니다.

이 경우 펌핑 길이 p는 펌핑할 수 있는 'a', 'b' 또는 'c'의 수입니다. 단순화를 위해 p = 2라고 하자. 이제 문자열 w = a^2 b^2 c^2를 고려하십시오. 이 문자열을 u = a^2, v = b^2, x = ε(빈 문자열), y = ε 및 z = c^2의 다섯 부분으로 나눌 수 있습니다.

이 경우 펌핑 속성의 조건이 충족됩니다.
1. 결합된 v와 y의 길이는 2보다 큽니다. |vxy| = |b^0| > XNUMX.
2. uvxy의 길이는 |uvxy|이므로 기껏해야 p입니다. = |a^2 b^2| ≤ 2.
3. 음수가 아닌 정수 k의 경우 문자열 uv^kxy^kz도 L에 있습니다. 예를 들어 k = 0을 선택하면 uv^0xy^0z = a^2 c^2가 됩니다. 엘.

따라서 언어 L = {a^nb^nc^n | n ≥ 0}은 펌핑 속성을 만족하며 상황에 따라 다릅니다.

일반적으로 CSL과 관련하여 펌핑 속성이 유지되는 조건은 다음과 같습니다.
1. v와 y를 합한 길이는 XNUMX보다 커야 합니다.
2. uvxy의 길이는 최대 펌핑 길이 p이어야 합니다.
3. 음수가 아닌 정수 k의 경우 문자열 uv^kxy^kz도 언어 L이어야 합니다.

이러한 조건은 언어가 상황에 맞는 경우 언어 구조를 유지하면서 문자열의 섹션을 반복하여 "펌핑"할 수 있도록 합니다.

기타 최근 질문 및 답변 상황에 맞는 언어:

상황에 맞는 언어에서 더 많은 질문과 답변 보기

더 많은 질문과 답변:

아래의 태그 : , , , , ,