펌핑 보조정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정규 언어에 대한 펌핑 보조정리
3. 문맥 자유 언어에 대한 펌핑 보조정리
참조

1. 개요

펌핑 보조정리는 정규 언어 및 문맥 자유 언어의 속성을 설명하는 데 사용되는 정리이다. 정규 언어에 대한 펌핑 보조정리는, 길이가 충분히 큰 문자열이 정규 언어에 속하려면 특정 조건을 만족하는 방식으로 분할될 수 있음을 나타낸다. 문맥 자유 언어의 경우, 길이가 충분히 큰 문자열은 다른 조건에 따라 분할될 수 있다. 이러한 정리는 언어가 정규 또는 문맥 자유인지 증명하는 데 사용될 수 있다.

2. 정규 언어에 대한 펌핑 보조정리

정규 언어에 대한 펌핑 보조정리는 어떤 언어가 정규 언어가 아님을 증명하는 데 사용된다.

2. 1. 내용

어떤 언어 ''L''이 정규 언어이고 무한하다고 할 때, 자연수 ''p'' > 0가 존재해서, 길이가 ''p'' 이상인 임의의 문자열 ''w'' ∈ ''L''를 다음 조건을 만족시키도록 ''w'' = ''xyz''와 같이 분할할 수 있다.

|''y''| > 0
|''xy''| ≤ ''p''
모든 i ≥ 0에 대해 ''xy''ⁱ''z'' ∈ ''L''

다시 말해, 길이가 충분히 큰 문자열이 정규 언어에 속하려면 반드시 ''xyz''의 형태로 표시되어서, ''y''를 i번 펌핑한 ''xy''ⁱ''z''도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:

\begin{array}{l}(\forall  L\subseteq \Sigma^*)  \\\quad      (\mbox{regular}(L) \Rightarrow \\\quad      ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land(\forall i\geq 0)(xy^iz\in L))))))))\end{array}

정규 언어는 하나의 결정적 유한 오토마톤으로 수락 가능한 모든 단어의 집합 ''L''로 정의된다. 동일한 정의로, 어떤 정규 표현식으로 기술되는 단어의 집합 등이 존재한다. 정규 언어의 반복 보조 정리(펌핑 보조 정리)는 다음 내용을 가리킨다.

임의의 정규 언어 ''L''에 대해, 1 이상의 값 ''r''이 존재하여, 길이 ''r'' 이상의 임의의 단어 ''w'' ∈ ''L''는 다음 조건을 만족하는 부분 문자열 ''x'', ''y'', ''z''에 의해 ''w'' = ''xyz''로 분할될 수 있다.

#

\vert xy\vert\leqq r

… ''xy''는 길이가 ''r'' 이하이다.

#

\vert y\vert\geqq 1

… ''y''는 빈 문자열이 아니다.

#

xy^iz \in L\;\;(i\geq 0)

… ''y''를 여러 번 반복한 문자열 ''xyy...yz''는 모두 ''L''의 단어이다.

2. 2. 조건

분할된 문자열 ''w'' = ''xyz''는 다음 조건을 만족해야 한다.^[1]

|''y''| > 0
|''xy''| ≤ ''p''
모든 i ≥ 0에 대해 ''xy''ⁱ''z'' ∈ ''L''

이를 엄밀히 기술하면 다음과 같다.

:

\begin{array}{l}(\forall  L\subseteq \Sigma^*)  \\\quad      (\mbox{regular}(L) \Rightarrow \\\quad      ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land(\forall i\geq 0)(xy^iz\in L))))))))\end{array}

정규 언어의 반복 보조 정리(펌핑 보조 정리)에 따르면, 임의의 정규 언어 ''L''에 대해, 1 이상의 값 ''r''이 존재하여, 길이 ''r'' 이상의 임의의 단어 ''w'' ∊ ''L''는 다음 조건을 만족하는 부분 문자열 ''x'', ''y'', ''z''에 의해 ''w'' = ''xyz''로 분할될 수 있다.^[1]

#

\vert xy\vert\leqq r

(''xy''는 길이가 ''r'' 이하이다.)

#

\vert y\vert\geqq 1

(''y''는 빈 문자열이 아니다.)

#

xy^iz \in L\;\;(i\geq 0)

(''y''를 여러 번 반복한 문자열 ''xyy...yz''는 모두 ''L''의 단어이다.)

2. 3. 엄밀한 기술

어떤 언어 ''L''이 정규 언어이고 무한하다고 하자. 그러면 자연수 ''p'' > 0가 존재해서, 길이가 ''p'' 이상인 임의의 문자열 ''w'' ∈ ''L''를 다음 조건을 만족시키도록 ''w'' = ''xyz''와 같이 분할할 수 있다.

|''y''| > 0
|''xy''| ≤ ''p''
모든 i ≥ 0에 대해 ''xy''ⁱ''z'' ∈ ''L''

이를 엄밀히 기술하면 다음과 같다.

:

\begin{array}{l}(\forall  L\subseteq \Sigma^*)  \\\quad      (\mbox{regular}(L) \Rightarrow \\\quad      ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land(\forall i\geq 0)(xy^iz\in L))))))))\end{array}

3. 문맥 자유 언어에 대한 펌핑 보조정리

문맥 자유 언어에 대한 펌핑 보조정리는 어떤 언어가 문맥 자유 언어가 아님을 증명하는 데 사용된다. 이는 문맥 자유 문법에 의해 생성되는 단어의 집합이나, 푸시다운 오토마타로 수락 가능한 모든 단어 집합으로 정의된다.

3. 1. 내용

어떤 언어 ''L''이 문맥 자유 언어이고 무한하다고 하자. 그러면 자연수 ''p'' > 0이 존재하여, 길이가 ''p'' 이상인 임의의 문자열 ''w'' ∈ ''L''를 다음 조건을 만족시키도록 ''w'' = ''uvxyz''와 같이 분할할 수 있다.

|''vy''| > 0
|''vxy''| ≤ ''p''
모든 i ≥ 0에 대해 ''uv''ⁱ''xy''ⁱ''z'' ∈ ''L''

다시 말해, 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 ''uvxyz''의 형태로 표시되어서, v와 y를 i번 펌핑한 ''uv''ⁱ''xy''ⁱ''z''도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:

\begin{array}{l}(\forall  L\subseteq \Sigma^*)  \\\quad      (\mbox{context-free}(L) \Rightarrow \\\quad      ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\\quad\quad ((\exists u,v,x,y,z \in \Sigma^*) (w=uvxyz \land (|vy| > 0 \land |vxy|\leq p \land(\forall i\geq 0)(uv^ixy^iz\in L))))))))\end{array}

문맥 자유 언어는 고정된 문맥 자유 문법에 의해 생성되는 단어의 집합으로 정의된다. 또는 (하나의) 푸시다운 오토마타로 수락 가능한 모든 단어 집합으로 정의된다. 문맥 자유 언어의 반복 보조정리는 다음 내용을 의미한다.

임의의 문맥 자유 언어 ''L''에 대해, 어떤 1 이상의 값 ''r''이 존재하여, 길이 ''r'' 이상의 임의의 단어 ''w'' ∊ ''L''는 다음 조건을 만족하는 부분 문자열 ''u'', ''v'', ''x'', ''y'', ''z''에 의해 ''w'' = ''uvxyz''로 분할될 수 있다.

1.

\vert vxy\vert\leqq r

… ''vxy''는 길이가 ''r'' 이하이다.

2.

\vert v\vert+\vert y\vert\geqq 1

… ''v''와 ''y'' 중 적어도 하나는 빈 문자열이 아니다.

3.

uv^ixy^iz \in L\;\;(i\geq 0)

… ''v''와 ''y''를 같은 횟수로 반복한 문자열 ''uvv…vxyy…yz''는 모두 ''L''의 단어이다.

3. 2. 조건

분할된 문자열 ''w'' = ''uvxyz''는 다음 조건을 만족해야 한다.

|''vy''| > 0
|''vxy''| ≤ ''p''
모든 i ≥ 0에 대해 ''uv''ⁱ''xy''ⁱ''z'' ∈ ''L''

3. 3. 엄밀한 기술

어떤 언어 ''L''이 문맥 자유 언어이고 무한하다고 하자. 그러면 자연수 ''p'' > 0이 존재하여, 길이가 ''p'' 이상인 임의의 문자열 ''w'' ∈ ''L''를 다음 조건을 만족시키도록 ''w'' = ''uvxyz''와 같이 분할할 수 있다.

|''vy''| > 0
|''vxy''| ≤ ''p''
모든 i ≥ 0에 대해 ''uv''ⁱ''xy''ⁱ''z'' ∈ ''L''

다시 말해, 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 ''uvxyz''의 형태로 표시되어서, v와 y를 i번 펌핑한 ''uv''ⁱ''xy''ⁱ''z''도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:

\begin{array}{l}(\forall  L\subseteq \Sigma^*)  \\\quad      (\mbox{context-free}(L) \Rightarrow \\\quad      ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\\quad\quad ((\exists u,v,x,y,z \in \Sigma^*) (w=uvxyz \land (|vy| > 0 \land |vxy|\leq p \land(\forall i\geq 0)(uv^ixy^iz\in L))))))))\end{array}

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com