[계산이론] - (12) 문맥 자유 문법의 단순화

 

 

 

문맥 자유 문법의 생성규칙의 우측에 나오는 문자열의 형태에는 어떠한 제약도 없습니다.

그러나 오히려 이런 제한으로 인해 복잡성이 증가하는 단점을 가집니다.

이제부터 저희는 이러한 제약 없는 문법 대신, 제한된 형태를 만족하는 동치인 문법으로 변형하는 방법을 살펴볼 것입니다.

 

 

 

 

 

 

문법의 변형 방법

빈 문자열(λ)이 나타나는 문법이나 언어는 다소 바람직하지 못합니다.

이는 많은 정리와 증명에서 별개의 역할을 하며, 특별히 주의하여야 합니다.

저희는 이러한 빈 문자열을 고려대상에서 제거하여 오직 λ를 포함하지 않는 언어만을 살펴보려 합니다.

 

 

L을 문맥 자유 언어라 하고, G를 L-{λ}(L 에서 빈 문자열 제거)을 생성하는 문맥 자유 문법이라 하겠습니다.

여기서 V에 새로운 시작 심벌을 추가하고 다음의 새로운 생성규칙을 P에 추가함으로써 L을 생성하는 문법을 얻을 수 있습니다.

$$S_0 \to S \;| \; \lambda$$

 

결과적으로 모든 실질적인 의미에 대하여, λ를 포함하는 문맥-자유 언어와 포함하지 않은 문맥-자유 언어 사이에는 차이가 없습니다.

따라서 앞으로는 λ를 포함하지 않는 문맥 자유 언어로 그 대상을 좁힐 것입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

유용한 치환 규칙

단순화란 어떤 형태의 바람직하지 않은 생성규칙들을 제거하는 것입니다.

문맥-자유 문법 G의 생성규칙 P가 다음과 같은 경우,
$$A \to x_1 B x_2$$

A와 B는 서로 다른 변수임을 가정하며, B를 좌변에 갖는 P의 모든 생성규칙들이 다음과 같다고 하면,
$$B \to y_1\;|\; y_2\; | \;...\; |\; y_n$$

$\hat{G} = (V, T, S, \hat{P})$ 를 $P$ 에서 $A \to x_1 B x_2$ 를 삭제하고, 다음의 생성규칙을 추가하여 얻어진 새로운 생성규칙들의 집합 $\hat{P}$ 를 갖는 문법이라 하겠습니다.
$$A \to x_1y_1x_2 \;|\;x_1y_2x_2 \;|\;...\;|\;x_1y_nx_2 $$


이때 위의 두 언어는 동치입니다.
$$L(\hat{G}) = L(G)$$

 A와 B가 다른 변수라는 사실이 꼭 필요합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

쓸모없는(Useless) 생성규칙

다음과 같은 생성 규칙을 살펴보겠습니다.

$$S \to aSb\; | \;\lambda \;| \;A$$
$$A \to aA$$

 

변수 A가 단말들의 문자열로 변환될 수 없기 때문에, 생성규칙 $S \to A$는 아무런 역할도 하지 못하는 것이 분명합니다.

A는 문장 형태에는 나타날 수 있으나, A는 문장으로는 도달할 수 없습니다.

이런 생성규칙을 제거하는 것은 생성되는 언어에 아무런 영향을 주지 않기 때문에, 하나의 단순화라고 볼 수 있습니다.

 

 

$G = (V, T, S, P)$ 를 문맥-자유 문법이라 하겠습니다.
변수 $A \in V$ 에 대하여, 다음 형태의 유도가 가능한 문자열 $w \in L(G)$ 가 적어도 하나 존재하고 오직 그럴 때에만 A가 쓸모있다고 합니다.
$$S \overset{*}{\Rightarrow} xAy \overset{*}{\Rightarrow} w$$

여기서 x와 y는 $(V \cup T)$에 속해 있습니다.

다시 말하면 변수가 적어도 하나의 유도에 나타나고, 오직 그럴 때에만 쓸모가 있습니다.
이렇지 않은 변수를 쓸모없다(useless)고 합니다.
생성규칙이 쓸모없는 변수를 포함하고 있으면 역시 쓸모가 없습니다.

 

 

변수가 쓸모없이지는 두 가지 이유는 다음과 같습니다

해당 변수가 시작 심벌로부터 도달할 수 없습니다.

해당 변수가 단말(terminal) 문자열을 유도해낼 수 없습니다.

 

 

 

 

 

 

 

 

 

 

 

 

종속 그래프 (dependency graph)

종속 그래프는 쓸모없는 변수와 생성규칙들을 제거하는 과정에서 사용될 수 있는 유용한 도구입니다.

문맥-자유 언어에 대하여 종속 그래프는 변수들이 라벨로 주어진 정점들을 가지며
정점들 C와 D 사이에는 다음과 같은 형태의 생성규칙이 존재하고, 오직 그럴 때에만 간선이 존재합니다.
$$C \to xDy$$

 

 

 

 

 

 

 

 

 

 

 

 

 

쓸모없는 생성규칙 제거 절차

$G = (V, T, S, P)$ 를 문맥-자유 문법이라 하면
어떤 쓸모 없는 변수와 생성규칙들을 포함하지 않고 G와 동치인 문법이 존재하며, 아래와 같습니다.
$$\hat{G} = (\hat{V}, \hat{T}, S, \hat{P})$$

이때 위 문법은 두 부분으로 이루어진 알고리즘에 의해 G로부터 생성될 수 있습니다.

첫 부분에서는 중간 단계의 문법 $G_1 = (V_1, T, S, P_1)$ 을 구성합니다.

여기서 $V_1$ 은 다음과 같은 유도가 가능한 변수 A들만으로 구성됩니다.
$$A \overset{*}{\Rightarrow} w \in T^{*}$$


이후 $G_1$ 에 대한 종속 그래프를 그린 후, 그래프에서 S로부터 도달될 수 없는 변수들을 찾아냅니다.

이들은 변수들의 집합에서 제거되고, 마찬가지로 그 변수들을 포함하는 생성규칙들도 제거됩니다.

이를 통해 단순화된 최종 문법을 얻어냅니다.

 

 

 

 

$G_1 = (V_1, T, S, P_1)$ 을 구성하는 방법은 다음과 같습니다.

1. $V_1$을 공집합으로 놓습니다.
2. 다음 단계를 $V_1$ 에 새로운 변수들이 추가되지 않을 때까지 반복합니다.

각 $A \in V$ 에 대해, P가 다음과 같은 형태의 생성규칙을 포함하면 A를 $V_1$에 추가합니다.
$$A \to x_1 x_2 ... x_m$$
여기서 모든 $x_i$ 는 $V_1 \cup T$ 에 속합니다.

3. P1을 P에 속한 생성규칙 가운데 모든 심벌들이 $V_1 \cup T$ 에 속하는 모든 생성규칙들로 구성합니다.

 

 

 

 

 

예시

 

 

 

위 과정을 설명하면 다음과 같습니다.

주어진 문법에 대해서 terminal symbol로만 이루어진 문자열(문장)을 유도할 수 없는 생성규칙을 제거합니다.
위의 예시의 경우 $C \to aCa$ 이므로, C는 문장을 유도할 수 없으며, 따라서 제거됩니다.
또한 C를 유도해내는 생성규칙도 같이 제거되어 $S \to C$ 인 생성규칙이 제거됩니다.

이렇게 문장을 만들 수 없는 생성규칙을 모두 제거한 이후, 종속 그래프를 그려 시작 변수로부터 도달할 수 없는 상태들을 지우면 끝입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$\lambda$ 생성규칙의 제거

다음과 같은 형태의 문맥-자유 문법의 생성규칙을 $\lambda$ -생성규칙이라 부릅니다.
$$A \to \lambda$$

다음과 같이 빈 문자열로 유도가 가능한 변수를 널가능(nullable) 변수라 부릅니다.
$$ A  \overset{*}{\Rightarrow}  \lambda $$

어떤 문법은 $\lambda$ 를 포함하지 않는 언어를 생성하지만,  $\lambda$ -생성규칙과 널가능 변수들을 갖고 있을 수 있습니다.
이런 $\lambda$ -생성규칙은 제거될 수 있습니다.


이때 우변에 나타나는 널가능 변수들의 모든 가능한 조합에 대하여,
람다로 대체하여 얻어지는 모든 생성규칙들을 추가한 후에 제거하여야 합니다.

 

 

 

 

 

 

 

 

 

 

 

$\lambda$ 생성규칙의 제거 절차

$V_N$ 을 널가능 변수들의 집합이라 설정합니다.

다음의 생성 규칙에 대하여 $A$ 를 $V_N$ 에 포함시킵니다.
$A \to \lambda$
$A \to $  variables  already  in $V_N$

$V_N$ 에 새로운 변수들이 추가되지 않을 때까지 위의 과정을 반복합니다.

이후 람다 생성규칙을 제거합니다.

이때 우변에 있는 널가능 변수들을 람다로 대체하여 얻어질 수 있는 모든 생성규칙들을 추가합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

단위-생성규칙의 제거

다음과 같은 형태의 문맥-자유 언어의 생성규칙을 단위-생성규칙이라 부릅니다.

다음과 같은 형태의 문맥-자유 언어의 생성규칙을 단위-생성규칙(unit-promotion)이라 부릅니다.
$$A \to B$$
여기서 A, B ∈ V 입니다.

 

 

 

 

 

 

 

 

 

 

 

단위-생성규칙의 제거 절차

문법의 모든 $A \to B$ 생성규칙(단위 생성규칙)에 해당하는 A에서 B까지의 간선을 갖는 종속 그래프를 그립니다.

단위 생성규칙을 제외하고 원래 문법의 모든 생성 규칙을 포함하는 새로운 문법을 구성합니다.

종속 그래프에 A에서 B로의 경로가 있을 때마다, 위에서 언급한 유용한 치환 규칙을 사용하여 B를 바꾸고 새 문법의 생성 규칙만 사용합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

단순화

위에서 배운 과정들을 종합하여 아래 단계를 순서대로 사용하면 문법을 단순화 할 수 있습니다.

• λ-생성규칙을 제거한다.
• 단위-생성규칙을 제거한다.
• 쓸모없는 생성규칙을 제거한다.
  • terminal을 만들지 못하는 생성규칙을 제거한다
  • 도달 불가능한 생성규칙을 제거한다

위 순서를 지키지 않을 경우, 간략화 과정에서 쓸모없는 규칙들이 다시 생성될 수 있으므로, 위 순서대로 간략화를 진행하셔야 좋습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Reference

https://www.youtube.com/watch?v=HqJHsnXxFhE&list=PLSN_PltQeOygPrInjCFdQM992AotARlFa&index=16