Properties of Context-Free Languages
문맥-자유 언어의 성질들
Two Pumping Lemmas (두 펌핑 보조 정리들)
Theorem 8.1 A Pumping Lemma for CFL
Infinite CFL \(L\)이 있다하자.
\(|w| \geq m\) 인 모든 \(w \in L\)에 대해,
\(|vxy| \leq m, |vy| \geq 1\)인 \(m\)에 대해
\(w = uvxyz\)
로 나타낼 수 있고, (분할할 수 있고,)
모든 \(i = 0, 1, 2, \cdots\)에 대해,
\(uv^ixy^iz \in L\) 이다.
(\(v, y\)가 Pumping된다.)
※ 이 Pumping Lemma는 어떠한 Language가 CFL군에 속하지 않음을 입증하는데 유용하다.
pf)
Language \(L - \{\lambda\}\)를 고려해보자.
이 Language에는 Unit-Production과 \(\lambda\)-Production이 없는 Grammar \(G\)가 있다 하자.
모든 생성규칙의 우변에 오는 문자열들의 길이는 한정되어 있으므로,
모든 \(w \in L\)에 대한 유도의 길이는 적어도 \({|w| \over k}\) 이어야 한다.
따라서, \(L\)은 무한 집합이므로, 임의의 긴 유도와 대응되는 임의의 높이의 Derivation Tree가 존재한다.
이 Derivation Tree의 루트에서부터 리프까지의 Path를 고려해보자.
\(G\)에 있는 변수의 개수는 유한하므로, 위 Path상에서 반복되는 변수가 반드시 하나 이상 존재한다.
아래와 같은 Derivation을 생각해보자.
\(S \Rightarrow^* uAz \Rightarrow^* uvAyz \Rightarrow^* uvxyz\)
여기서 \(u, v, x, y, z\)는 모두 Terminal들로 이루어진 String이다.
위 Derivation에서 \(A \Rightarrow^* vAy와 A \Rightarrow^* x\) 임을 유추해낼 수 있다.
(즉, \(v\)와 \(y\)가 Pumping될 수 있다.)
따라서 모든 String \(uv^ixy^iz (i = 0, 1, 2, \cdots)\) 이 \(G\)에 의해 생성될 수 있고, \(L\)에 속함을 알 수 있다.
\(x\)를 생성하는 Subtree에서는 어떠한 변수도 Pumping되지 않는다.
또한, \(v, y\)를 생성하는 Subtree에서는 Pumping되는 변수가 없다 가정할 수 있다.
그러나, \(w\)의 \(v, x, y\)의 길이는 오직 \(G\)의 생성규칙에 달렸고, \(w\)와는 독립적이기 때문에,
\(|vxy| \leq m\) 조건은 타당하다.
또한, \(G\)에는 Unit-Production과 \(\lambda\)-Production이 없으므로,
\(w\)의 \(v\)와 \(y\)는 동시에 Empty String일 수 없기 때문에 \(|vy| \geq 1\)이 타당하다.
Example.
Grammar가 아래와 같을 때,
\(A \to BC \; | \; a\\
B \to BA \; | \; b\\
C \to BA\)
(위 Grammar는 CNF이다.)
\(w = uvxyz\)에서
\(u = b\\
v = bb\\
x = a\\
y = \lambda\\
z = ba\)
이다.
여기서, G가 CNF인 경우, \(m \leq 2^n\) 이다.
(\(n\) : 변수의 개수)
Example 8.1
\(L = \{a^nb^nc^n : n \geq 0\}\) 일 때,
\(L\)은 CFL이 아니다.
pf)
\(L\)에 속한 임의의 String \(w = a^mb^mc^m\)을 생각해보자.
\(vxy\)가 \(a\)로만 이루어진 String이라면,
Pumping된 String이 \(L\)에 속하지 않음은 자명하다.
(\(a\)의 개수와 \(b\)의 개수, \(c\)의 개수가 모두 같아야 \(L\)에 속하기 때문이다.)
\(v, y\)가 같은 개수의 \(a\)와 \(b\)를 포함한다면,
\(k \neq m\)인 Pumped String \(w_i = a^kb^kc^m\)이 생성될 수 있고,
이 또한 \(L\)에 속하지 않는다.
임의의 Pumped String이 \(L\)에 속하려면,
\(v, y\)에 같은 개수의 \(a, b, c\)가 포함되도록 하는 \(vxy\)를 선택해야 하지만,
이는 \(|vxy| \leq m\) 조건에 위배되므로, 불가능하다.
따라서, \(L\)은 CFL이 될 수 없다.
* \(L = \{a^nb^n : n \geq 0\}\) 에 대한 논의
결론적으로, \(L\)은 CFL이기 떄문에 \(L\)에 속하는 어떠한 String을 Pump시켜도 \(L\)에 속하게 된다.
임의의 String \(w = a^mb^m\)이 있다하자.
\(v = a^k, y = b^k\) 일 때,
어떤 \(i\)를 고르던, Pumped String \(w_i\)는 \(L\)에 속하게 된다.
(그러나, Pumping Lemma를 통해 \(L\)이 CFL임을 증명할 수는 없다.
Pumping Lemma는 \(L\)이 CFL이 아닌 경우를 입증할 수 있게하는 수단이다.)
* \(\widehat{L} = \{a^nb^n : n \geq 0\} \cup \{a^nb^{2n} : n \geq 0\} \cup \{a^nb^nc^n : n \geq 0\}\) 에 대한 논의
임의의 String \(w = a^mb^mc^m\)은 \(\widehat{L}\)에 속한다.
하지만 Pumped String \(w_i\)는 \(\widehat{L}\)에 속하지 않는다.
따라서, \(\widehat{L}\)은 CFL이 아니다.
Example 8.2
\(L = \{ww : w \in \{a, b\}^*\}\)은 CFL이 아니다.
pf)
임의의 String \(w = a^mb^ma^mb^m\) 이라 하자.
\(w\)는 \(L\)에 속한다.
\(u = a^k \qquad (k < m)\\
v = a^{m-k}\\
x = b^j \qquad (j < m)\\
y = b^{m-j}\\
z = a^mb^m\)
이라 하면,
\(i = 0\) 일 때,Pumped String \(w_0 = a^kb^ja^mb^m\) 이고,
\(w_0\)은 \(L\)에 속하지 않는다.
따라서, \(L\)은 CFL이 아니다.
Example 8.3
\(L = \{a^{n!} : n \geq 0\}\) 은 CFL이 아니다.
pf)
임의의 \(w = a^{m!}\)가 있다 하자.
\(v = a^k\)
\(y = a^l\)
이라 할 때,
Pumped String \(w_0 = uxz\)에 대하여,
\(|w_0| = m! - (k+l)\) 이다.
\(w_0\)가 \(L\)에 속하려면, \(|w_0|\)이 \(j!\) (임의의 수의 팩토리얼) 형태이어야 한다.
즉, \(m! - (k+l) = j!\) 이어야 한다.
하지만 Pumping Lemma의 조건에 의해, \(k+l \leq m\) 이고,
\((m-1)! < m! - m \leq m! - (k+j) = |uxz| < m! 이므로,\)
\(|w_0|\)은 어떤 수의 팩토리얼 값이 될 수 없고, \(w_0\)은 \(L\)에 속하지 않는다.
즉, \(L\)은 CFL이 아니다.
Example 8.4
\(L = \{a^nb^j : n = j^2\}\) 는 CFL이 아니다.
pf)
임의의 String \(w = a^{m^2}b^m\) 이 있다 하자.
\(v = a^{k_1}\\
y = b^{k_2}\)
라 하면,
\(n_a(w_i) = m^2 + (i-1)k_1\) 이고,
\(n_b(w_i) = m + (i-1)k_2\) 인,
\(w_i\)가 정해진다.
\(k_1, k_2 \neq 0\)이고, \(i = 0\)인 경우,
\((m-k_2)^2 \leq (m-1)^2\\
\qquad = m^2 - 2m + 1\\
\qquad < m^2 - k_1 \qquad (\because k_1 \leq m - 1 \therefore k_1 \leq 2m - 1)\)
(Pumping Lemma 조건에 의해, \(k_1 + k_2 \leq m, k_1 \geq 1, k_2 \geq 1\) 임에 유념하자.)
이므로, Pumped String \(w_0\)은 \(L\)에 속하지 않는다.
즉, \(L\)은 CFL이 아니다.
A Pumping Lemma for Linear Languages
Definition 8.1 Linear Language
\(L = L(G)\)인 Linear CFG \(G\)가 존재하면,
CFL \(L\)을 Linear Language라 한다.
※ 모든 Linear Language는 CFL이다.
※ Grammar가 Linear하지 않다 해서, 해당 Grammar가 생성하는 언어가 Linear하지 않음을 의미하지는 않는다.
- 어떤 Language가 Linear함을 보이려면,
해당 Language를 생성한 Grammar와 동치인 Linear Grammar가 존재하지 않음을 입증해야 한다.
(Linear Language에 대한 구조적 성질을 정립하고, 몇몇 CFL이 요구되는 성질을 충족시키지 못함을 보인다.)
Example 8.5
\(L = \{a^nb^n : n \geq 0\}\)은 Linear Language이다.
단, \(L = \{w : n_a(w) = n_b(w)\}\)는 Linear Language가 아니다.
Theorem 8.2
Infinite Linear Language \(L\)이 있다 하자.
\(|w| \geq m\)인 모든 \(w \in L\)은
\(|uvyz| \leq m \qquad\) ( \(|vxy| \leq m\) 이 아님에 유의하자. )
\(|vy| \geq 1\) 이고,
모든 \(i = 0, 1, 2, \cdots\) 에 대해
\(uv^ixy^iz \in L\)을 만족시키는
\(w = uvxyz\)로 표현(분할)될 수 있다.
pf)
\(L\)이 Linear Language이므로,
\(L\)을 생성하는 Linear Grammar \(G\)가 존재한다.
편의를 위해, \(G\)에는 Unit-Production, \(\lambda\)-Production이 없다 가정하자.
(Linear Grammar에서 Unit-Production과 \(\lambda\)-Production을 제거해도 Linear Grammar이다.)
String \(w \in L(G)\)에 대해,
\(S \Rightarrow^* uAz \Rightarrow^* uvAyz \Rightarrow^* uvxyz = w\)
와 같이 유도된다 하자.
모든 \(w \in L(G)\)에 대해,
아래 3가지 성질을 모두 만족하는 변수 \(A\)가 있다하자.
1) \(S \Rightarrow^* uAz\) 에서 어떤 변수도 반복되지 않는다.
2) \(S \Rightarrow^* uAz \Rightarrow^* uvAyz\) 에서 \(A\)를 제외한 어떤 변수도 반복되지 않는다.
3) \(A\)의 반복은 첫 \(m\)단계 안에서 발생되어야 한다.
여기서 \(m\)은 \(w\)에 의해 주어진 것이 아니라, Grammar에 의한 것이다.
변수 \(A\)가 존재하면, \(u, v, y, z\)의 길이는 \(w\)와는 독립적이게 된다.
Example 8.6
\(L = \{w : n_a(w) = n_b(w)\}\) 는 Linear Language가 아니다.
pf)
\(L\)이 Linear Language라 가정하자.
임의의 String \(w = a^mb^{2m}a^m\) 이 있다 하자.
\(|uvyz| \leq m\) 조건에 의해,
\(u, v, y, z\)는 모두 \(a\)로만 구성되어야 한다.
여기서, \(v, y\)가 Pump되면,
\(a^{m+k}b^{2m}a^{m+1}\) 을 얻게되고, 이는 \(L\)에 속하지 않는다.
(\(k \geq 1\) 또는 \(l \geq 1\))
즉, \(L\)은 Linear Language가 아니다.
Closure Properties and Decision Algorithms for Context-Free Languages
(문맥-자유 언어에 대한 폐포 성질과 결정 알고리즘)
※ Regular Language에서 성립되는 Closure Property들이 CFL에 대해 항상 성립하지는 않는다. 이에 유의하자.
Theorem 8.3 Closure of CFL
CFL은 Union(합집합, \(\cup\)), Concatenation(접합, \(\cdot\)), Star-Closure(스타-폐포, \(L^*\))에 대한 Closure-Property가 성립한다.
pf)
CFG \(G_1 = (V_1, T_1, S_1, P_1)\) 에 의해 생성되는 CFL \(L_1\),
CFG \(G_2 = (V_2, T_2, S_2, P_2)\) 에 의해 생성되는 CFL \(L_2\) 가 있다 하자.
이 때, \(V_1 \cap V_2 = \phi\) 이다. (즉, 서로소이다.)
1) Closure Property of Union Operation
Grammar \(G_3 = (V_1 \cup V_2 \cup \{S_3\}, T_1 \cup T_2, S_3, P_3)\)가 있다 하자.
여기서 \(S_3\)는 \(V_1 \cup V_2\)에 속하지 않는 변수이다.
\(G_3\)의 생성규칙 \(P_3\)는 \(G_1\)과 \(G_2\)의 모든 생성규칙들과
두 Grammar들 가운데 하나만을 사용하는 또 다른 시작 생성규칙으로 구성되어 있다.
즉, \(P_3 = P_1 \cup P_2 \cup \{S_3 \to S_1 \; | \; S_2\}\) 이다.
자명하게도, \(G_3\)는 CFG이다.
따라서 \(L(G_3)\)는 CFL이며,
\(L(G_3) = L_1 \cup L_2\) 임을 확인할 수 있고,
이는 CFL에 대해 Union(합집합, \(\cup\)) 연산에 대한 Closure Property가 성립됨을 의미한다.
예를 들어, \(w \in L_1\)이라 하자.
\(S_3 \Rightarrow S_1 \Rightarrow^* w\) 은 Grammar \(G_3\)에 파생될 수 있는 Derivation이다.
또한, \(w \in L_2\)인 경우에도,
\(S_3 \Rightarrow S_2 \Rightarrow^* w\) 와 같이 \(G_3\)에 의해 파생될 수 있는 Derivation이 가능하다.
만약, \(w \in L(G_3)\)이면,
Derivation의 첫 단계로 \(S_3 \Rightarrow S_1\) 혹은 \(S_3 \Rightarrow S_2\) 이어야 한다.
이 때, \(V_1 \cap V_2 = \phi\) (서로소)이므로,
\(S_1 \Rightarrow^* w\) 은 \(P_1\)의 생성규칙에 의해서만 가능한 Derivation이고,
\(S_2 \Rightarrow^* w\)는 \(P_2\)의 생성규칙에 의해서만 가능한 Derivation이다.
즉, \(w\)는 Unambiguous하다. \(w\)는 \(L_1\)에 속하거나, \(L_2\)에 속한다.
즉, \(L(G_3)\)는 \(L_1\)과 \(L_2\)의 합집합으로 구성된 Language이다.
2) Closure Property of Concatenation Operation
Grammar \(G_4 = (V_1 \cup V_2 \cup \{S_4\}, T_1 \cup T_2, S_4, P_4)\)가 있다 하자.
여기서 \(S_4\)는 \(V_1 \cup V_2\)에 속하지 않는 변수이고,
\(P_4 = P_1 \cup P_2 \cup \{S_4 \to S_1S_2\}\) 이다.
따라서, \(L(G_4) = L(G_1)L(G_2)\) 이고,
\(L(G_4)\)는 \(L_1\)과 \(L_2\)의 접합으로 구성된 Language이다.
3) Closure Property of Star-Closure Operation
\(G_5 = (V_1 \cup \{S_5\}, T_1, S_5, P_5)\)
여기서 \(S_5\)는 \(V_1\)에 속하지 않는 변수이고,
\(P_5 = P_1 \cup \{S_5 \to S_1S_5 \; | \; \lambda \}\) 이다.
따라서, \(L(G_5) = L(G_1)^*\) 이고,
\(L(G_5)\)는 \(L_1\)의 스타-폐포로 구성된 Language이다.
* Summary
\(L_1 \cup L_2 : G = (V_1 \cup V_2 \cup \{S\}, T_1 \cup T_2, S, P_1 \cup P_2 \cup \{S \to S_1 \; | \; S_2\})\\
L_1 \cdot L_2 : G = (V_1 \cup V_2 \cup \{S\}, T_1, \cup T_2, S, P_1 \cup P_2 \{S \to S_1S_2\})\\
L_1^* : G = (V_1 \cup \{S\}, T_1, S, P_1 \cup \{S \to S_1S \; | \; \lambda\})\)
Theorem 8.4
CFL은 Intersection Operation(교집합, \(\cap\))과 Complementation Operation(여집합, \(\bar{L}\), \(L'\))에 대해
Closure Property가 성립되지 않는다.
pf)
Language \(L_1 = \{a^nb^nc^m : n \geq 0, m \geq 0\}\) 와
Language \(L_2 = \{a^nb^mc^m : n \geq 0, m \geq 0\}\) 이 있다 하자.
\(L_1\)과 \(L_2\)는 CFL이다.
(\(L_1\)과 \(L_2\)를 생성하는 Grammar는 생략한다.)
그러나,
\(L_1 \cap L_2 = \{a^nb^nc^n : n \geq 0\}\)
가 CFL아님은 Example 8.1에서 입증되었다.
따라서, CFL에 대해 교집합 연산은 Closure Property가 성립되지 않는다.
또한, \((L_1' \cup L_2')' = L_1 \cap L_2\) 이고,
\(L_1 \cap L_2\)가 CFL이 아니므로, 좌변의 Complementation으로 이루어진 Language 또한 CFL이 아니다.
즉, CFL에 대해 여집합 연산은 Closure Property가 성립되지 않는다.
※ 그러나, CFL \(L_1\)과 Regular Language \(L_2\)에 대해, \(L_1 \cap L_2\)는 CFL이다.
- Regular Language은 CFL의 Subset이다.
- 즉, Regular Language \(\cap\) CFL = Regular Language 이기 때문에,
정규 교집합 연산은 Closure Property가 성립하는 것이다.
Theorem 8.5 Closure Property of Regular Intersection (정규 교집합에 대한 Closure Property)
CFL \(L_1\)과 Regular Language \(L_2\)에 대해,
\(L_1 \cap L_2\)는 CFL이다.
pf)
\(L_1\)을 Accept하는 NPDA \(M_1 = (Q, \Sigma, \Gamma, \delta_1, q_0, z, F_1)\) 이 있고,
\(L_2\)를 Accpet하는 DFA \(M_2 = (P, \Sigma, \delta_2, p_0, F_2)\) 가 있다 하자.
PDA \(\widehat{M} = (Q \times P, \Sigma, \Gamma, \widehat{\delta}, (q_0, p_0), z, F_1 \times F_2)\)는
\(M_1\)과 \(M_2\)를 Parallel하게 수행하는 Automata이다.
여기에,
\(((q_k, q_l), x) \in \widehat{\delta}((q_i, p_j), a, b)\\
\iff (q_k, x) \in \delta_1(q_j, a, b) = p_l 이고, \delta_2(p_j, a) = p_l\)
(단, \(a = \lambda\)이면, \(p_j = p_l\) 이다. DFA는 \(\lambda\) Transition을 허용하지 않기 때문이다.)
즉, Input String의 한 Symbol을 읽어낼 때 마다, \(\widehat{M}\)은 \(M_1\)과 \(M_2\)의 Transition을 동시에 수행하고,
\(\widehat{M}\)의 State는 \(M_1\)과 \(M_2\)의 State들의 Pair로 구성된다.
또한,
\(q_r \in F_1 과 p_s \in F_2\)에 대해,
\(((q_0, p_0), w, z) \vdash^*_{\widehat{M}} ((q_r, p_s), \lambda, x)\\
\iff (q_0, w, z) \vdash^*_{M_1} (q_r, \lambda, x) 이고, \delta^*(p_0, w) = p_s\)
이다.
즉,
\(w\)가 \(L(M_1) \cap L(M_2) = L_1 \cap L_2\)에 속한다.
\(\iff w\)는 \(\widehat{M}\)에 의해 Accpet된다.
이다.
※ 한 FA는 다수의 FA를 동시에 Simulation할 수 있지만, 한 PDA는 다수의 PDA를 동시에 Simulation할 수 없다.
- 한 Stack이 다수의 Stack을 Simulation할 방법이 없기 때문이다.
Example 8.7
\(L = \{a^nb^n : n \geq 0, n \neq 100\}\) 은 CFL이다.
pf)
이는 \(L\)을 Accept하는 PDA를 보이거나, CFG를 구성하여 증명할 수도 있다.
본 포스트에서는 Theorrem 8.5를 이용하여 \(L\)이 CFL임을 입증한다.
\(L_1 = \{a^{100}b^{100}\}\) 이라 하자.
\(L_1\)은 Finite하므로, Regular Language이다.
또한,
\(L = \{a^nb^n : n \geq 0\} \cap L_1'\) 이다.
여집합에 대한 Regular Language에 대한 Closure Property가 성립하고,
정규 교집합에 대해 CFL은 Closure Property가 성립하므로,
\(L\)은 CFL임을 알 수 있다.
Example 8.8
\(L = \{w \in \{a, b, c\}^* : n_a(w) = n_b(w) = n_c(w)\}\) 은 CFL이 아니다.
pf)
\(L\)이 CFL이라 가정하면,
\(L(a^*b^*c^*)\)은 Regular Language이므로,
\(L \cap L(a^*b^*c^*) = \{a^nb^nc^n : n \geq 0\}\) 또한 CFL이어야 한다.
그러나, Example 8.1에서 \(\{a^nb^nc^n : n \geq 0\}\)는 CFL이 아님이 입증되었다.
따라서 \(L\)은 CFL이 아니다.
※ Pumping Lemma를 이용하여 \(L\)이 CFL이 아님을 입증할 수도 있다.
Decidable Properties of CFL
Theorem 8.6
CFG \(G = (V, T, S, P)\)에 대해,
\(L(G)\)가 \(\phi\)인지 아닌지를 결정하는 알고리즘이 존재한다.
pf)
편의를 위해, \(\lambda \notin L(G)\)라 가정하자.
만약, \(S\)가 Useless Variable이면, \(L(G) = \phi\)이다.
그렇지 않은 경우, \(L(G)\)에는 적어도 한 개 이상의 원소가 존재한다.
Theorem 8.7
CFG \(G = (V, T, S, P)\)에 대해,
\(L(G)\)가 무한집합인지 아닌지를 결정하는 알고리즘이 존재한다.
pf)
편의를 위해, \(G\)에는 \(\lambda\)-Production, Unit-Production, Useless-Production이 없다 가정한다.
\(G\)에는
\(A \Rightarrow^* xAy\)
와 같은 Derivation이 가능한 어떤 \(A \in V\)가 존재한다.
\(G\)에는 \(\lambda\)-Production, Unit-Production이 존재하지 않기 때문에,
\(x\)와 \(y\)는 동시에 Empty String이 될 수 없다.
즉, \(A\)가 Empty String, Useless Symbol도 아니기 때문에
\(S \Rightarrow^* uAv \Rightarrow^* w\) 과
\(A \Rightarrow^* z\) 와 같은 Derivation이 가능하다.
(\(u, v, z \in T^*\))
따라서, 모든 \(n\)에 대해
\(S \Rightarrow^* uAv \Rightarrow^* ux^nAy^nv \Rightarrow^* ux^nzy^nv\)
와 같은 Derivation이 가능하다.
즉, \(L(G)\)는 무한집합이다.
만약, 어떠한 변수도 반복되지 않는 경우,
모든 Derivation의 길이는 \(|V|\)로 한정되며,
이 경우 \(L(G)\)는 유한집합이다.
※ 즉, Grammar가 반복되는 변수를 포함하는지를 살피면, \(L(G)\)가 무한집합인지 아닌지를 판별할 수 있다.
- 이는 Dependency Graph에서 Cycle을 찾는 방법으로 더욱 쉽게 확인할 수 있다.
Undecidable Properties of CFL
CFG \(G_1, G_2\)에 대해,
\(L(G_1) = L(G_2)\) 의 여부를 판별하는 알고리즘은 존재하지 않는다.
Reference: An Introduction to Formal Languages and Automata 6E (Peter Linz 저, Jones & Bartlett Learning, 2017)
