Simplification of Context-Free Grammars and Normal Forms
문맥-자유 문법의 단순화와 정규형
* Simplication for Context-Free Grammars (단순화)
- 필요없는 변수와 생성규칙을 제거하는 과정을 의미한다.
1. \(\lambda\)-Production을 제거한다. (Theorem 6.3)
2. Unit-Production을 제거한다. (Theorem 6.4)
3. Useless Production을 제거한다. (Theorem 6.2)
* 편의를 위해, 이 장에서는 Language \(L\)이 \(\lambda\)를 생성하지 않는다고 가정한다.
- 만약 \(\lambda\)를 생성하는 경우를 고려해야 한다면, 기존의 생성규칙의 시작변수 \(S\)에 대해,
아래 생성규칙을 추가하면 된다.
\(S_0 \to S \; | \; \lambda\)
Methods for Transforming Grammars (문법의 변형 방법)
Theorem 6.1
CFG \(G = (V, T, S, P)\) 의 \(P\)가 아래와 같다.
\(A \to x_1Bx_2\)
\(B \to y_1 \; | \; y_2 \; | \; \cdots \; | \; y_n\)
\(\widehat{G} = (V, T, S, \widehat{P})\)에서 \(\widehat{P}\)는
\(P\)에서 \(a \to x_1Bx_2\)를 제거하고,
\(A \to x_1y_1x_2 \; | \; x_1y_2x_2 \; | \; \cdots \; | \; x_1y_nx_2\) 를 추가한
생성규칙이라 하자.
(즉, 변수 \(B\)에 대한 생성규칙들을 \(A\)에 병합하여 변수를 줄인 생성규칙임을 의미한다.)
이 때, \(L(\widehat{G}) = L(G)\) 가 성립한다.
pf)
어떤 \(w \in L(G)\) 가 존재한다 가정하면,
\(G\)에 의한 Derivation을 의미하는, \(S \Rightarrow^{*}_{G} w\) 와 같은 Derivation이 존재한다.
즉,
\(S \Rightarrow^*_G u_1Au_2 \Rightarrow_G u_1x_1Bx_2u_2 \Rightarrow_G u_1x_2y_jx_2u_2\)
이며,
\(S \Rightarrow^*_{\widehat{G}} u_1Au_2 \Rightarrow_{\widehat{G}} u_1x_1y_jx_2u_2\)
이다.
따라서, \(G\)와 \(\widehat{G}\)가 동일한 Sentential Form에 도달함을 알 수 있다.
즉, \(w \in L(G)\) 이면, \(w \in L(\widehat{G})\) 임이 성립되고, 역 또한 성립한다.
Example 6.1
Grammar \(G = (\{A, B\}, \{a, b, c\}, A, P)\) 에서 \(P\)는 아래와 같다.
\(A \to a \; | \; aaA \; | \; abBc\)
\(B \to abbA \; | \; b\)
여기서 변수 \(A\)의 생성규칙의 우변에 있는 변수 \(B\)에 대해,
Theorem 6.1에서의 치환을 적용한 생성규칙 \(\widehat{P}\)는 아래와 같다.
\(A \to a \; | \; aaA \; | \; ababbAc \; | \; abbc\)
즉,
\(A \Rightarrow_G aaA \Rightarrow_G aaabBc \Rightarrow_G aaabbc\) 이며,
\(A \Rightarrow_{\widehat{G}} aaA \Rightarrow_{\widehat{G}} aaabbc\) 이다.
즉, \(G\)와 \(\widehat{G}\)는 동치이다.
Definition 6.1 "Useful", "Useless"
CFG \(G = (V, T, S, P)\)가 있다 하자.
변수 \(A \in V\)에 대해
\(S \Rightarrow^* xAy \Rightarrow^* w\) Derivation이 가능하다. \(\iff w \in L(G)\)
를 만족하는 \(A\)를 "Useful 하다." 라고 표현한다.
여기서, \(x, y \in (V \cup T)\) 이다.
즉, 변수가 적어도 하나의 Derivation에서 나타나고,
궁극적으로 String을 생성할 수 있으면
해당 변수는 Useful하다.
반면, 어떤 Derivation에도 나타날 수 없거나(시작 Symbol로 부터 도달할 수 없거나)
Terminal Symbol을 유도하지 못하는 변수를 "Useless 하다." 라고 표현한다.
Example.
\(S \to aSb \; | \; \lambda \; | \; A\\
A \to aA\)
위와 같은 문법에서,
\(A \to aA\)는 Useless하다.
Example 6.2
시작 Symbol이 \(S\)인 아래 생성규칙을 보자.
\(S \to A\)
\(A \to aA \; | \; \lambda\)
\(B \to bA\)
여기서, 변수 \(B\)는 Terminal Symbol을 유도할 수는 있지만,
\(S \Rightarrow^* xBy\) 와 같은 Derivation에는 존재하지 않으므로,
변수 \(B\)와 생성규칙 \(B \to bA\)는 Useless하다.
Theorem 6.2 Removing Useless Production
CFG \(G = (V, T, S, P)\) 이다.
어떠한 Useless한 변수 혹은 생성규칙을 포함하지 않으며,
\(G\)와 동치인 Grammar \(\widehat{G} = (\widehat{V}, \widehat{T}, S, \widehat{P})\) 가 존재한다.
pf)
\(G\)를 통해 \(\widehat{G}\) 를 생성하기에 앞서,
중간 단계의 Grammar인 \(G_1 = (V_1, T, S, P)\) 를 구성한다.
여기서, \(V_1\)은
\(A \Rightarrow^* w \in T^*\)
와 같은 Derivation이 가능한 변수 \(A\)들만 포함된다.
(즉, 궁극적으로 String을 생성할 수 있는 변수들이 \(V_1\)에 포함된다.)
\(G\)를 \(G_1\)로 구성하는 Procedure은 아래와 같다.
1. \(V_1\)을 \(\phi\)로 둔다.
2. 각 \(A \in V\)에 대해, \(P\)가 \(A \to x_1x_2 \cdots x_m\) 과 같은 생성규칙을 포함하면 \(A\)를 \(V_1\)에 추가한다.
(여기서 모든 \(x_i \in (V_1 \cup T)\) 이다.)
이를 \(V_1\)에 새로운 변수들이 추가되지 않을 때 까지 반복한다.
(Symbol들을 생성할 수 있는 변수들만 \(V_1\)에 추가하고, 나머지 변수들은 모두 버린다.)
3. \(P\)에 속한 생성규칙들 중, 모든 Symbol들이 \(V_1 \cup T\)에 속하는 모든 생성규칙들을 \(P_1\)으로 구성한다.
(시작 변수로 부터 도달 불가능한 변수들을 버린다.)
* 요약
1. \(V_1\)을 공집합으로 초기화한다.
2. Symbol, Terminal을 생성할 수 없는 변수와 생성규칙들을 버린다.
3. 시작 변수에 도달되지 않는 변수와 생성규칙을 버린다.
위 Procedure을 거친 후,
\(A \Rightarrow^*_{G_1} w \in T^*\) 와 같은 Derivation이 가능함은 명백하며,
\(A \Rightarrow^*_{G_1} w = ab\cdots\) 를 만족하는 모든 \(A\)가 위 Procedure내에 \(V_1\)에 속하게 됨은
Partial Derivation Tree를 그려서 확인할 수 있다. (Reference pp.175-176.)
마지막으로,
\(G_1\)을 통해 \(\widehat{G}\)를 구성한다.
\(G_1\)에 대한 Variable Dependency Graph(변수 종속 그래프)를 그려서
\(S\)로부터 도달될 수 없는 변수들을 찾아낸다.
이 변수들을 변수들의 집합에서 제거하고,
이러한 변수들을 포함하는 생성규칙들도 제거한다.
그 결과, \(\widehat{G}\)를 얻어낼 수 있다.
\(\widehat{G}\)는 어떠한 Useless한 변수, 생성규칙을 포함하지 않으며,
\(w \in L(G)\)에 대해, \(S \Rightarrow^* xAy \Rightarrow^* w\)
와 같은 Derivation이 존재한다.
\(\widehat{G}\)의 구성에서 \(A\)와 관련된 생성규칙들이 유지되기 떄문에,
\(S \Rightarrow^*_{\widehat{G}} xAy \Rightarrow^*_{\widehat{G}} w\)
와 같은 Derivation에 필요한 변수, 생성규칙 등을 \(\widehat{G}\)가 갖고 있다.
따라서, \(L(G) \subseteq L(\widehat{G})\) 이 성립한다.
또한, \(\widehat{G}\)는 \(G\)에서 생성규칙들을 제거하여 얻어지는 Grammar이므로,
\(\widehat{P} \subseteq P\) 이다.
즉, \(G\)와 \(\widehat{G}\)는 동치이다.
Example 6.3
\(V = \{S, A, B, C\}, \quad T = \{a, b\}\) 이며
생성규칙 \(P\)는 아래와 같다.
\(S \to aS \; | \; A \; | \; C\)
\(A \to a\)
\(B \to aa\)
\(C \to aCb\)
\(V_1 = \{A, B, S\}\\(P_1)\\S \to aS \; | \; A\\A \to a\\B \to aa\)
\(\widehat{V} = \{S, A\}\\(\widehat{P})\\S \to aS \; | \; A\\A \to a\)
변수 \(B\)는 시작 Symbol \(S\)로부터 유도될 수 없어 Useless하고,
변수 \(C\)는 Terminal Symbol을 유도할 수 없어 Useless하다.
Definition 6.2 \(\lambda\)-Production, Nullable Variable
- CFG에서
\(A \to \lambda\)
와 같은 생성규칙을 \(\lambda\)-Production이라 한다.
\(A \Rightarrow^* \lambda\) 와 같이,
빈 문자열로 유도가 가능한 변수를
Nullable Variable이라 한다.
\(\lambda\)를 생성하는 Language는 아니지만,
\(\lambda\)-Production과 Nullable Variable을 갖고 있는 Language의 경우,
\(\lambda\)-Production은 제거될 수 있다.
Example 6.4
\(S \to aS_1b\)
\(S_1 \to aS_1b \; | \; \lambda\)
와 같은 Grammar에서 시작 변수는 \(S\)라 하자.
위 Grammar는 Language \(\{a^nb^n : n \geq 1\}\) 을 생성한다.
\(\lambda\)-Production인 \(S_1 \to \lambda\) 는
우변에 있는 \(S_1\)을 \(\lambda\)로 치환하여 얻어진 생성규칙들을 추가한 후에 제거될 수 있다.
즉,
\(S \to aS_1b \; | \; ab\)
\(S_1 \to aS_1b \; | \; ab\)
와 같은 Grammar로 수정할 수 있다.
Theorem 6.3
\(G\)를 \(\lambda\)를 생성하지 않는 CFG라 하자.
이 때,
\(\lambda\)-Production을 갖고있지 않고, \(G\)와 동치인 Grammar \(\widehat{G}\)가 존재한다.
pf)
\(G\)의 모든 Nullable Variable들의 집합 \(V_N\)을 구하는 Procedure는 아래와 같다.
1. 모든 생성규칙 \(A \to \lambda\) 에 대해, \(A\)를 \(V_N\)에 포함시킨다.
2. \(B \to A_1A_2\cdots A_n\) 에 대해, \(A_1, A_2, \cdots, A_n\) 들이 모두 \(V_N\)에 포함되어 있을 경우, \(B\)를 \(V_N\)에 포함시킨다.
이 단계를 \(V_N\)에 새로운 변수가 추가되지 않을 때 가지 반복한다.
\(P\)에 있는
\(A \to x_1x_2\cdots x_m, \quad (m \geq 1, x_i \in (V \cup T))\)
형태의 생성규칙과
우변에 위치하는 Nullable Variable들을
가능한 모든 조합으로 \(\lambda\)를 생성할 수 있는 모든 생성규칙들을
\(\widehat{P}\)에 추가한다.
예를 들어,
\(x_i, x_j\)가 Nullable Variable인 경우,
\(x_i\)만을 이용하여 \(\lambda\)를 생성하는 생성규칙,
\(x_j\)만을 이용하여 \(\lambda\)를 생성하는 생성규칙,
\(x_i, x_j\) 둘 다 이용하여 \(\lambda\)를 생성하는 생성규칙
모두를 \(\widehat{P}\)에 추가한다.
단, 모든 \(x_i\)가 Nullable하면, 생성규칙 \(A \to \lambda\) 는 \(\widehat{P}\)에 포함되지 않는다.
Example 6.5
\(S \to ABaC\)
\(A \to BC\)
\(B \to b \; | \; \lambda\)
\(C \to D \; | \; \lambda\)
\(D \to d\)
위 Grammar와 동치이면서, \(\lambda\)-Production을 갖지않는 CFG를 구하라.
Sol)
Nullable Variable은 \(A, B, C\)이다.
즉, \(V_N = \{A, B, C\}\) 이며,
모든 가능한 조합을 고려하여 \(A, B, C\)를 \(\lambda\)로 치환하여 구한 Grammar는 아래와 같다.
\(S \to ABaC \; | \; BaC \; | \; AaC \; | \; ABa \; | \; aC \; | \; Aa \; | \; Ba \; | \; a \\
A \to B \; | \; C \; | \; BC \\
B \to b \\
C \to D \\
D \to d \)
즉, \(S \to ABaC\) 에서는 \(A, B, C\)를 \(\lambda\)로 치환하는 경우의 수가 \(2^3 = 8\) 가지로 나오며,
(\(A, B, C\)가 동시에 \(\lambda\)로 치환되어도, Symbol \(a\)가 있기 때문에 \(\lambda\)-Production이 되지 않는다.)
\(A \to BC\)에서는 \(B, C\)를 \(\lambda\)로 치환하는 경우의 수가 \(2^2 - 1 = 3\) 가지로 나온다.
(\(B, C\)가 동시에 \(\lambda\)로 치환되면, \(\lambda\)-Production이 되기 때문에 허용되지 않는다.)
※ Example 6.5를 진행하고 난 후, Unit-Production이 생성됨을 관측할 수 있다.
- 즉, Unit-Production 제거는 \(\lambda\)-Production 제거가 선행된 이후에 행해져야 한다.
- 또한, Unit-Production을 제거하는 과정에서 특정 변수가 시작변수로부터 도달 불가능해 지는 경우가 있다. (Example 6.6)
이러한 이유때문이라도, \(\lambda\)-Production 제거가 먼저 이루어져야 한다.
Definition 6.3 Unit-Production
\(A \to B \qquad (A, B \in V)\)
와 같은 CFL의 생성규칙을
Unit-Production이라 한다.
Unit-Production은 Derivation에서 별다른 의미를 갖지 않으므로, 제거할 수 있다.
Theorem 6.4
\(\lambda\)-Production을 가지지 않는 CFG \(G = (V, T, S, P)\)가 있다 가정하자.
이 때,
Unit-Production을 갖고 있지 않으며, \(G\)와 동치인
CFG \(\widehat{G} = (\widehat{V}, \widehat{T}, S, \widehat{P})\)가 존재한다.
pf)
\(A \to A\) 형태의 모든 Unit-Production을 곧바로 제거되어도 Grammar에 아무 영향을 미치지 않음이 자명하므로,
\(A \to B\) 형태의 Unit-Production의 제거를 고려하자.
우선, \(P\)에서 Unit_production이 아닌 모든 생성규칙을 \(\widehat{P}\)에 포함시킨다.
Theorem 6.1의 방법 (해당 변수가 생성하는 Terminal Symbol들로 변수를 대체하는 방법)은
\(A \to B\\
B \to A\)
와 같은 Unit-Production들을 제거하지 못하는 문제점을 가진다.
이 문제를 해결하기 위해,
모든 \(A\)에 대해,
\(A \Rightarrow^* B\)
를 만족시키는 모든 변수 \(B\)를 찾는다.
(이는 \(A\)와 \(B\)사이에 Walk가 존재하는지에 대한 여부를 판단하여 알아낼 수 있다.)
이들을 찾기 위해, Unit-Production들로만으로 Dependency Graph를 그려서 찾아낸다.
구해진 \(A\)와 \(B\)들에 대하여,
\(A \to y_1 \; | \; y_2 \; | \; \cdots \; | \; y_n\)
와 같은 생성규칙을 \(\widehat{P}\)에 포함시킨다.
단,
\(B \to y_1 \; | \; y_2 \; | \; \cdots \; | \; y_n\) 은
\(\widehat{P}\)에서 \(B\)를 좌변에 갖는 모든 생성규칙들이다.
이들은 \(\widehat{P}\)에서 취한 생성규칙들이므로,
어느 \(y_i\)도 단일 변수가 될 수 없고,
그 말은 Unit-Production이 만들어지지 않음을 의미한다.
Example 6.6
\(S \to Aa \; | \; B\\
B \to A \; | \; bb\\
A \to a \; | \; bc \; | \; B\)
위와 같은 Grammar의 모든 Unit-Production을 제거하라.
Sol)
먼저, 위 Grammar에서 Unit-Production이 아닌 생성규칙들을 정제하면 아래와 같다.
\(S \to Aa\\
A \to a \; | \; bc\\
B \to bb\)
이들은 곧바로 \(\widehat{G}\)에 포함된다.
Unit-Production들을 통해 Dependency Graph를 그리면 아래와 같다.
위 Dependency Graph를 통해 알아낸,
Unit-Production Pairs들의 Derivation은 아래와 같다.
\(S \Rightarrow^* A\\
S \Rightarrow^* B\\
B \Rightarrow^* A\\
A \Rightarrow^* B\)
이 Pairs들이 만들어낸 새로운 생성규칙들은 아래와 같다.
\(S \to a \; | \; bc \; | \; bb\\
A \to bb\\
B \to a \; | \; bc\)
이들 또한, \(\widehat{G}\)에 포함시킨다.
즉, \(\widehat{G}\)는 아래와 같다.
\(S \to a \; | \; bc \; | \; bb \; | \; Aa\\
A \to a \; | \; bb \; | \; bc\\
B \to a \; | \; bb \; | \; bc\)
(Unit-Production을 제거하여 \(B\)와 연관된 생성규칙들이 Useless해졌다.)
※ Unit-Production을 제거하는 과정에서 특정 변수(B)가 시작 변수로 부터 도달 불가능해지는 경우가 생길 수 있다.
이로 인해, \(\lambda\)-Production 제거가 Unit-Production 제거보다 선행되어야 한다.
Theorem 6.5
\(\lambda\)를 포함하지 않는 CFL \(L\)이 있을 때,
\(L\)을 생성하면서,
Useless Production, \(\lambda\)-Production, Unit-Production을 갖지 않는 CFG가 존재한다.
pf)
아래와 같은 순서로 진행하면,
우리가 제거하고자 하는 생성규칙들을 문제없이 제거해나갈 수 있다.
1. \(\lambda\)-Production을 제거한다. (Theorem 6.3)
2. Unit-Production을 제거한다. (Theorem 6.4)
3. Useless Production을 제거한다. (Theorem 6.2)
Two Important Normal Forms (정규형)
Chomsky Normal Form (CNF; Chomsky 정규형)
- 생성규칙의 우변에 있는 Symbol들의 개수를 두 개 이하가 되도록 하는 정규형이다.
Definition 6.4 Chomsky Normal Form (CNF)
CFG \(G\)에서 모든 생성규칙이
\(A \to BC\) 혹은 \(A \to a \qquad (A, B, C \in V, a \in T)\)
와 같은 형태를 만족하면,
\(G\)를 Chomsky Normal Form이라 한다.
Example 6.7
\(S \to AS \; | \; a \\
A \to SA \; | \; b\)
위 문법은 Chomsky Normal Form이다.
\(S \to AS \; | \; AAS\\
A \to SA \; | \; aa\)
위 문법은 Chomsky Normal Form이 아니다.
Theorem 6.6
\(\lambda\)-Production과 Unit-Production을 갖지않는
CFG \(G = (V, T, S, P)\)에 대해,
\(G\)와 동치이면서, Chomsky Normal Form인
Grammar \(\widehat{G} = (\widehat{V}, \widehat{T}, S, \widehat{P})\)가 존재한다.
pf)
아래 두 단계를 거쳐 \(G\)를 Chomsky Normal Form인 \(\widehat{G}\)로 변환할 수 있다.
Step 1. 길이가 2 이상인 생성규칙들에 있는 모든 Terminal Symbol들을 새로 도입한 변수들로 대체하여
Terminal Symbol들을 제거하는 과정
\(G\)의 생성규칙들 중,
\(A \to x_1x_2\cdots x_n \qquad (x_i \in (V \cup T))\)
(\(n=1\)인 경우에, \(G\)는 Unit-Production을 갖지 않아야 하므로, \(x_1\)은 Terminal Symbol이어야 한다.)
(\(n \geq 2\)인 경우에, \(T\)에 속한 모든 Terminal Symbol \(a\)을, 새로운 변수 \(B_a\)로 대체한다.)
와 같은 형태의 생성규칙을 만족하는 모든 생성규칙들을 고려하면서
\(G\)를 \(G_1 = (V_1, T, S, P_1)\)으로 변환한다.
예를 들어,
\(A \to BaAb\) 와 같은 생성규칙을
\(A \to BB_aAB_b\) 와 같이, 새로운 변수로 대체하여
\(P_1\)에 포함시킨다.
위의 형태를 만족하는 \(P\)의 모든 생성규칙들에 대해,
\(A \to C_1C_2\cdots C_n \qquad (x_i \in V\)인 경우, \(C_i = x_i\)이고, \(x_i = a\)인 경우, \(C_i = B_a)\)
와 같은 생성규칙을 \(P_1\)에 포함시킨다.
각 변수 \(B_a\)에 대해,
\(B_a \to a\)
를 \(P_1\)에 포함시킨다.
최종적으로
\(A \to a\)
혹은
\(A \to C_1C_2\cdots C_n\)
형태의 생성규칙들로만 구성된 Grammar \(G_1\)이 생성된다.
즉, \(L(G_1) = L(G)\) 이다.
Step 2. 생성규칙의 우변에 두 개의 변수들만 위치하도록 생성규칙을 조정하는 과정
\(A \to a\\
A \to C_1C_2\cdots C_n\)
형태이고, \(n = 2\)인 생성규칙들을 \(\widehat{P}\)에 포함시킨다.
\(n > 2\)인 경우, 새로운 변수 \(D_1, D_2, \cdots D_n\)을 생성하여
\(A \to C_1D_1\\
D_1 \to C_2D_2\\
\vdots\\
D_{n-2} \to C_{n-1}C_n\)
형태의 생성규칙들을 \(\widehat{P}\)에 포함시킨다.
예를 들어,
\(A \to BB_aAB_b\)
와 같은 생성규칙을
\(A \to BD_1\\
D_1 \to B_aD_2\\
D_2 \to AB_b\)
로 대체하여 \(\widehat{P}\)에 포함시킨다.
\(\widehat{G}\)는 명백히 Chomsky Normal Form이며,
\(L(G_1) = L(\widehat{G})\)이며,
\(L(\widehat{G}) = L(G)\) 이다.
Example 6.8
\(S \to ABa\\
A \to aab\\
B \to Ac\)
를 CNF로 변환한다.
CNF의 요구사항대로, 위 Grammar는 \(\lambda\)-Production과 Unit-Production을 갖고있지 않다.
Step 1. 길이가 2 이상인 생성규칙들에 있는 모든 Terminal Symbol들을 새로 도입한 변수들로 대체하여
Terminal Symbol들을 제거하는 과정
새로운 변수 \(B_a, B_b, B_c\)를 도입하여,
\(S \to ABB_a\\
A \to B_aB_aB_b\\
B \to AB_c\\
B_a \to a\\
B_b \to b\\
B_c \to c\)
와 같이, Terminal Symbol들을 Variable로 대체한다.
Step 2. 생성규칙의 우변에 두 개의 변수들만 위치하도록 생성규칙을 조정하는 과정
Step 1에서의 1~2번 생성규칙을 Normal Form으로 변환하기 위해
새로운 변수 \(D_1, D_2\)를 도입하여
최종적으로, 아래와 같은 Chomsky Normal Form을 구성한다.
\(S \to AD_1\\
D_1 \to BB_a\\
A \to B_aD_2\\
D_2 \to B_aB_b\\
B \to AB_c\\
B_a \to a\\
B_b \to b\\
B_c \to c\)
Greibach Normal Form (GNF; Greibach 정규형)
- 생성규칙의 우변에 있는 String의 길이에는 제한이 없으나,
Variable과 Terminal Symbol의 위치에 제한을 두는 정규형이다.
Definition 6.5 Greibach Normal Form (GNF)
CFG \(G\)에서 모든 생성규칙이
\(A \to ax \qquad (a \in T, x \in V^*)\)
형태를 만족하면 G를 Greibach Normal Form이라 한다.
※ S-Grammar의 조건과 비슷하나, Greibach Normal Form에서는 Pair \((A, a)\)가 하나만 존재해야 한다는 제약이 없다.
Example 6.9
\(S \to AB\\
A \to aA \; | \; bB \; | \; b\\
B \to b\)
위 Grammar는 Greibach Normal Form이 아니다.
Theorem 6.1의 치환 규칙을 이용하여
\(S \to aAB \; | \; bBB \; | \; bB\\
A \to aA \; | \; bB \; | \; b\\
B \to b\)
위와 같이, 기존의 Grammar와 동치인 Grammar로 변환할 수 있고,
위 Grammar는 Greibach Normal Form이다.
Example 6.10
\(S \to abSb \; | \; aa\)
를 Greibach Normal Form으로 변환한다.
변환 방법은 Chomsky Normal Form으로의 변환 방법을 사용한다.
Terminal Symbol \(a, b\) 각각에 대해,
두 변수 \(A, B\)를 사용한다.
Terminal들을 연관된 변수로 치환하면
\(S \to aBSB | aA\\
A \to a\\
B \to b\)
로 변환할 수 있다.
변환한 Grammar는 기존의 Grammar와 동치이면서, 동시에 Greibach Normal Form이다.
Theorem 6.7
\(\lambda\)를 생성하지 않는 모든 CFG \(G\)에 대해,
동치인 Greibach Normal Form Grammar \(\widehat{G}\)가 존재한다.
- 변환하는 알고리즘 또한 존재하나, 복잡해서인지 책에는 소개되어 있지 않다...
A Membership Algorithm for Context-Free Grammars (문맥-자유문법에 대한 소속성 알고리즘)
CYK Algorithm
- J.Cocke, D. H. Younger, T. Kasami가 개발한, Dynamic Programming 타입의 알고리즘이다.
- Chomsky Normal Form에 의해 생성된 모든 Language의 Membership을 결정짓는다.
- 즉, Grammar가 Chomsky Normal Form인 경우에만 올바르게 동작한다.
- \(V_{ij}\)의 원소의 유도과정을 기록하여, Parsing 방법으로 활용할 수 있다.
- CYK 알고리즘은 \({n(n+1) \over 2}\)개의 \(V_{ij}\) 집합들에 대한 계산이 \(O(n^3)\)의 단계로 수행된다.
(즉, String \(w\)를 Parsing하는데 \(O(|w|^3)\)에 비례하는 시간을 소모하는 알고리즘이다.)
Chomsky Normal Form으로 주어진 Grammar \(G = (V, T, S, P)\)를 통해
String \(w = a_1a_2\cdots a_n\)
이 생성되었다 하자.
\(w_{ij} = a_i\cdots a_j\) 라 하고,
\(V\)의 Subset \(V_{ij}\)를
\(V_{ij} = \{A \in V : A \Rightarrow^* w_{ij}\}\) 라 하자.
(\(V_{ij}\) : \(w_{ij}\)를 생성할 수 있는 변수들의 집합)
이 때, \(w \in L(G) \iff S \in V_{1n}\) 이다.
즉, \(V_{ij}\)를 계산함에 있어, \(A \to a_i \iff A \in V_{ii}\) 인 것이다.
따라서, 모든 \(1 \leq i \leq n\) 에 대하여,
\(V_{ii}\)는 \(w\)와 Grammar의 생성규칙들을 검사하여 계산해낼 수 있다.
\(j > i\)에 대해, \(i \leq k \leq j\) 인 어떤 \(k\)에 대해,
\(B \Rightarrow^* w_{ik}\) 와
\(C \Rightarrow^* w_{k+1j}\)를 만족하는
생성 규칙 \(A \to BC\)가 존재 \(\iff A\)가 \(w_{ij}\)를 유도할 수 있다.
(즉, 변수 \(B\)와 \(C\)가 \(w_{ij}\)를 두 부분으로 나누어서 Parsing한다.)
즉, 아래와 같이 표현할 수 있다.
\(V_{ij} = \bigcup_{k \in \{i, i+1, \cdots, j-1\}} \{A | A \to BC, B \in V_{ik}, C \in V_{k+1, j}\}\)
예를 들어,
\(V_{ik} = \{X, Y\}\)
\(V_{k+1, j} = \{U, V\}\) 인경우
\(V_{ij}\)에는 우변에 \(XU, XV, YU, YV\)중 하나 이상을 갖는 변수들이 포함된다.
\(V_{ij}\)를 계산하는 과정은 아래와 같다.
1. \(V_{11}, V_{22}, \cdots, V_{nn}\)을 계산한다.
2. \(V_{12}, V_{23}, \cdots, V_{n-1,n}\)을 계산한다.
3. \(V_{13}, V_{24}, \cdots, V_{n-2, n}\)을 계산한다.
\(\qquad \vdots\)
(\(i\)와 \(j\)의 차이를 점점 벌려나아간다.)
이들을 계산하고,
\(w \in L(G) \iff S \in V_{1n}\) 를 이용하여
\(G\)가 \(w\)를 Parsing할 수 있는지를 알아낼 수 있다.
(여기서, \(S\)는 시작변수이다.)
Example 6.11
\(S \to AB\\
A \to BB \; | \; a\\
B \to AB \; | \; b\)
위 Grammar가
String \(w = aabbb\)를 Parsing할 수 있는지를 확인한다.
Dynamic Programming 방식으로, \(i\)와 \(j\)의 차이가 작은 값부터 계산해간다.
\(w_{11} = a\)이므로,
\(V_{11}\) 은 \(w_{11} = a\)를 직접 유도하는 모든 변수들의 집합이다.
즉, \(V_{11} = \{A\}\)가 된다.
또한, \(w_{22} = a\)이므로,
\(V_{22} = \{A\}\)가 되고,
이러한 과정으로 아래와 같은 결과를 도출해낼 수있다.
\(V_{11} = \{A\}
V_{22} = \{A\}\\
V_{33} = \{B\}\\
V_{44} = \{B\}\\
V_{55} = \{B\}\)
\(V_{12}\)는 아래와 같이, 정의를 통해 계산이 가능하다.
\(V_{12} = \{A | A \to BC, B \in V_{11}, C \in V_{22}\} = \phi\)
\(\because V_{11} = V_{22} = \{A\}\)이기 때문에, \(V_{12}\)는 우변에 \(AA\)를 갖는 생성규칙의 좌변에 위치한 변수들의 집합이다.
그러나 우변에 \(AA\)를 갖는 생성규칙이 없으므로, \(V_{12}\)는 공집합이다.
\(V_{23}\)은 아래와 같이, 정의를 통해 계산이 가능하다.
\(V_{23} = \{A | A \to BC, B \in V_\{22\}, C \in V_{33}\} = \{S, B\}\)
\(\because V_{23}\)은 우변에 \(AB\)를 갖는 생성규칙의 좌변에 위치한 변수들의 집합이며,
이 변수들에는 \(S\)와 \(B\)가 있기 때문이다.
위와 같은 방식을 통해 계산을 진행하면,
아래와 같은 결과를 도출할 수 있다.
\(V_{12} = \phi\\
V_{23} = \{S, B\}\\
V_{34} = \{A\}\\
V_{45} = \{A\}\)
\(V_{13}\)은 아래와 같이, 정의를 통해 계산이 가능하다.
\(V_{13} = \{A | A \to BC, (B \in V_{11}, C \in V_{23}) \; \mathrm{or} \; (B \in V_{12}, C \in V_{33})\}\)
\(V_{11} = A, V_{23} = \{S, B\}\)이므로,
우변에 \(AS\) 혹은 \(AB\)가 위치하는 변수가 \(V_{13}\)에 추가된다.
즉, \(S, B\)가 \(V_{13}\)에 추가된다.
\(V_{12} = \phi, V_{33} = B\)이다.
\(V_{12}\)가 공집합이므로, 이러한 형태의 변수를 생성하는 변수가 없다.
최종적으로 \(V_{13}\)은 \(S, B\)로 구성된다.
위와 같은 방식을 통해 계산을 진행하면,
아래와 같은 결과를 도출할 수 있다.
\(V_{13} = \{S, B\}\\
V_{24} = \{A\}\\
V_{35} = \{S, B\}\)
\(V_{14} = \{A\}\\
V_{25} = \{S, B\}\)
\(V_{15} = \{S, B\}\)
따라서 \(w \in L(G)\) 이다.
(\(\because S \in V_{1n}\))
| \(V_{ij}\) | j = 1 | j = 2 | j = 3 | j = 4 | j = 5 |
| i = 1 | A | \(\phi\) | S, B | A | \(V_{1,5}\) = S, B |
| i = 2 | - | A | S, B | A | S, B |
| i = 3 | - | - | B | A | S, B |
| i = 4 | - | - | - | B | A |
| i = 5 | - | - | - | - | B |
Reference: An Introduction to Formal Languages and Automata 6E (Peter Linz 저, Jones & Bartlett Learning, 2017)
