[오토마타] 16. 문법 변환 - Simplify CFG

기존의 CFG는 화살표 왼쪽 부분만 single variable 이기만 하면 되므로 문법 표현이 자유로웠다.

하지만 그런 문법으로 표현하는 언어는 너무 자유도가 높아서 파싱하는데 시간이 오래 걸리는 단점이 있었다.

(지난 글에서 p^(2w+1) 으로 계산했었다.)

 

그래서 이번 글에서는 파싱을 좀 더 편하게 하기 위해 CFG가 표현할 수 있는 언어의 범위를 제한하지 않으면서 문법을 간단하게 바꿀 수 있는 방법들을 정리해본다.

 

우선 첫 번째 방법은 기존의 CFG 문법을 유지하면서 이 문법을 단순화 하는 방법을 알아본다.

두 번째 방법으로는 normal form 으로 바꿔서 문법을 표현하는 방법을 알아본다.

 

이때 편의를 위해서 지금부터 변환하는 문법은 모두 문장으로 λ 를 갖지 않는, λ-free language 만을 생각한다.

지난 글에서도 잠깐 정리했었지만, 만약 λ-free language에 대해 파싱을 간단하게 할 수 있는 문법을 생각했다면, 그 언어에 λ 를 추가하는 것은 시작 변수 S를 produce하는 변수 S0 를 두고, S0 → S | λ 와 같은 produce를 통해 간단하게 λ를 추가할 수 있기 때문이다.

 

 

 

이를 수업 중에는 이렇게 표현해주셨다.

λ를 제외한 언어의 문법을 정의했을 때, 이 문법에 λ 를 고려하도록 수정하는 것은 매우 간단하므로 이제부터는 λ를 포함하지 않는 언어에 대해 파싱을 간단하게 하기 위한 문법 변환 방법을 정리해본다.

 

Simplify CFG

A useful subsitution rule

먼저 문법을 단순화할 때 유용한 규칙을 하나 살펴보자.

어떤 문법의 Productions 들에 이런 Production이 있다고 해보자.

 

A → x1 B x2

B → y1 | y2 | ... | yn ( A ≠ B )

 

다음과 같이 문법을 바꾸어도 같은 언어를 생성하는 문법을 만들 수 있다.

 

1. P에서 A → x1 B x2 를 제거한다.

2. A → x1 y1 x2 | x1 y2 x2 | .... | x1 yn x2 를 추가한다.

 

이때 헷갈리지 않도록 주의할 점은 B → y1 | ... | yn 은 지우지 않았다는 것이다.

왜냐하면 다른 변수가 B를 사용하고 있을 수 있다.

(즉, B라는 변수가 아예 사라진 것은 아니다.)

 

 

그렇다면 한번 예제를 풀어보자.

주어진 문법의 G^ 문법을 구했을 때, aaabbc 를 문장으로 가지는지 판별해보자.

 

 

A → abBc 에서 B 변수 자리에 B 에서 produce 하는 표현을 넣었다.

그러면 P^ 을 위와 같이 작성할 수 있다.

 

그런데 이렇게 작성하고 보니 Start Variable 인 A에서 B를 produce 하는 경우가 없기 때문에 B → 형태의 production을 제거할 수 있다.

 

이제 G와 G^ 에 대해 aaabbc를 유도해보면

 

G : A ➡ aaA ➡ aaabBc ➡ aaabbc

G^ : A ➡ aaA ➡ aaabbc

 

둘 다 aaabbc를 유도할 수 있다.

 

---

Removing Useless Rule

위 예시에서 B가 아예 사용되지 않아서 제거할 수 있다고 했던 것처럼,

비록 사용이 되기는 하지만 그 자체로 문장을 만들 수 없어서 제거가 가능한 경우도 있다.

 

 

예를 들어 위 문법의 4개 production 중 A → aA 와 S → A는 제거할 수 있다.

왜냐하면 A 라는 변수는 항상 A라는 변수를 남겨두기 때문에 terminal 이 없어서 절대 끝날 수 없기 때문이다.

즉, setence를 만들 수 없는 production 이다.

 

이제 조금 더 명확하게 useless 에 대해서 정의해보자.

 

어떤 문법 G의 변수 A는 만약 L(G) 에 속하는 문장 w를 유도하는 과정에서

A가 한번이라도 활용이 된다면 useful 하고, 그렇지 않다면 useless 하다.

 

그리고 useless 개념을 variable 에서 production으로 확장했을 때는 다음과 같이 정의한다.

 

어떤 문법 G의 프로덕션에 속하는 p가 useless variable을 포함한다면, p는 useless하다.

 

쓸모없는 변수를 포함한 프로덕션은 역시 쓸모없다는 뜻으로, 직관적으로 이해하기 쉽다.

 

그렇다면 어떤 변수가 useful 한지, 아닌지를 어떻게 판별할 수 있을까?

위 정의를 보면 문장 w를 유도하는 과정에서 변수가 사용되어야 한다고 하였다.

이 말은 크게 2가지 조건을 만족해야 한다는 것을 알 수 있다.

 

G = (V, T, S, P) 에 대해서 변수 A가 useful 하다는 것은

 

1. S로부터 A를 유도할 수 있고,

2. A로부터 터미널 스트링을 유도할 수 있다.

 

이때 꼭 터미널 스트링이 문장일 필요는 없다.

 

 

위 예시를 보면, S 에서 출발하여 A 라는 변수가 유도되고, A는 그 자체로 터미널 스트링을 만들 수 있으므로 useful 하다.

반면 B는 S로부터 유도될 수 없으므로 B → aA 라는 프로덕션은 useless 하다.

 

 

주어진 문법에서 useless production 을 제거해보자.

1. S에서 닿을 수 없는 변수 제거

S 에서 B는 닿을 수 없으므로 B → aa 는 useless production 이다.

 

이를 확인할 때는 dependency graph를 그려서 확인해볼 수도 있다.

dependency graph는 변수를 노드로 하고, 하나의 변수가 다른 변수를 produce 하면 그 방향으로 간선을 추가하여 그릴 수 있다.

C는 useless로 판별해서 제거한 상태에서 그린 그래프

 

따라서 B는 S에서 닿을 수 없다.

 

2. terminal string을 유도할 수 없는 변수 제거

C 는 언제나 C를 남기므로 terminal string을 유도할 수 없다.

따라서 S → C, C → aCb 는 useless production 이다.

 

이 방법을 통해 모든 CFG에서 useless production 이 없는 동등한 G를 유도할 수 있다.

---

 

지난 글에서 컴퓨터에게 막 시켜서 파싱하는 방법을 적용했을 때, 파싱이 안 끝나는 원인으로 sentential form의 길이가 늘어나지 않도록 하는 production들이 존재하는 것을 꼽았었다.

그리고 그런 production들은 λ를 produce 하거나, single variable 에서 single variable을 그대로 produce 하는 production 이라고 정리했었다.

 

이제 문법을 단순화하기 위해서 위에서 말한 production 들도 차근차근 제거해보자.

 

Remove λ-production

λ-production은 말 그대로 λ를 produce하는 production을 말한다. (A → λ)

이때 λ-production과 관련하여 nullable 이라는 특성이 존재한다.

만약 어떤 변수로부터 λ 가 유도된다면, 해당 변수는 nullable하다고 표현한다.

 

또한 이로부터 λ-free language인 L(G)에 대해, 항상 λ-production이 없는 G^ 이 존재한다는 정리가 존재한다.

λ-production을 제거하는 방법은 간단하다.

1. 모든 nullable variable 을 Vn 이라는 변수 집합으로 묶는다.

2. 이를 이용하여 새로운 문법을 정의한다. (구체적인 방법은 예시로 설명한다.)

 

 

위 예시를 살펴보자.

S 에서부터 만들어지는 언어를 보면, ab, aabb, aaabbb, ... 와 같은 문장들이 만들어진다.

즉 L = { aⁿbⁿ : n ≥ 1 }  이다.

 

이 언어는 λ-free language 이므로 λ-production을 제거할 수 있다.

따라서 이를 반영한 새로운 문법은 아래와 같이 쓸 수 있다.

 

S → aSb | ab

 

이 예시는 간단해서 새로운 문법을 바로 작성해보았는데,

위 정리에 나온 λ-production을 제거하는 방법에 따라서 풀어보면 새로운 문법을 아래와 같은 순서로 만들 수 있다.

 

1. 모든 nullable 변수를 하나의 Vn 집합에 넣는다.

S1 은 λ를 만드므로 nullable 하다.

S는 λ를 만들지 않으므로 nullable 하지 않다.

 

2. 모든 nullable 변수를 produce 하는 production에 대해, 해당 변수 자리에 λ를 포함하는 production도 추가한다.

S → aS1b 에서 S1은 nullable 하므로 S1 자리에 λ 를 넣은 ab도 production으로 추가한다.

S1 →aS1b 역시 S1 → ab를 추가할 수 있다.

 

따라서 G^을 다음과 같은 production을 갖는 문법으로 작성할 수 있다.

 

S → aS1b | ab,

S1 → aS1b | ab

 

이 문법에는 더 이상 λ-production이 존재하지 않는다.

(위에서 직관적으로 바꾼 문법과는 다른 형태이지만 같은 언어를 나타낸다.)

 

 

나는 다음과 같이 풀었다.

 

 

파란색으로 밑줄친 부분이 새로 생성한 production 이다.

 

1. nullable 변수 찾기

A, B, C 가 nullable 하다.

 

2. S, A 에 대해서 3개의 nullable 변수에 대해 모든 null 경우의 수를 조합하여 production을 기술

(A만 null, B만 null, ...., AB가 null, ..., BC가 null, ABC 모두 null) 을 고려하여 그때의 production을 모두 기술한다.

 

 

Remove Unit-Production

unit-production 은 single variable 에서 single variable 을 유도하는 형태 ( A → B ) 를 말한다.

모든 CFG는 unit-production을 제거한, 동등한 문법 G를 가질 수 있다.

 

unit-production을 제거하는 방법은 다음과 같다.

1. 자기 자신에 대한 unit-production 제거 (A → A)

2. non unit-production들을 새로운 P^ 에 추가

3. A →* B 가 되는 모든 경우에 대해, A로부터 produce 하는 결과물에 'unit-production을 제외한 B의 production 결과'를 추가한다.

이때 경우의 수는 dependency graph를 그려서 모든 경우를 확인한다.

 

 

한번 예제를 풀어보자.

위 문법에서 unit-production을 제거한 문법은 다음과 같이 만들 수 있다.

 

1. 자기 자신에 대한 unit-production을 제거한다.

(없음)

 

2. 모든 non unit-production 을 P^에 추가한다.

S → Aa,

B → bb

A → a | bc

 

3. 모든 A →* B 꼴에 대해 A에 useful subtitution rule을 적용한다.

Dependency Graph를 그려보면 다음과 같이 그려진다.

 

 

이를 통해 다음의 경우가 존재함을 확인할 수 있다.

S →* A

S →* B

A →* B

B →* A

 

이제 기존의 P^에 하나씩 production을 추가해보자.

 

3-1. S →* A

unit-production을 제외하고 다음과 같이 추가할 수 있다.

S → Aa | a | bc

 

3-2. S →* B

마찬가지로 unit-production을 제외하고 다음과 같이 추가할 수 있다.

S → Aa | a | bc | bb

 

3-3. A →* B

A → a | bc | bb

 

3-4. B →* A

B → bb | a | bc

 

최종 문법은 

S → Aa | a | bc | bb

A → a | bc | bb

B → bb | a | bc

 

A, B 가 같은 터미널을 produce 하고 있어서 뭔가 이상하긴 하지만, 분명히 unit-production을 모두 없앤, 기존 문법과 동등한 문법이다.

---

정리

문법을 바꾸는 이유 : 파싱 비용 감소

문법을 바꾸는 방법 : CFG를 단순화 / normal form으로 바꾸기

 

<CFG를 단순화 하는 방법>

0. 특정 프로덕션에서 변수 없애기 (useful subtitution rule)

- A → xBy 라면 B가 produce 하는 것들을 모두 B 대신 대입하면, 이 프로덕션에서 B가 제거됨

- 하지만 'B → ...' 형태의 프로덕션은 여전히 필요할 수 있음

 

1. useless production 제거

- useless production : useless 변수를 포함하는 production

- useless 변수는 S에서부터 닿을 없거나 / 그 자체로 터미널 스트링을 만들 수 없는 변수

 

2. λ-production 제거

- 유도했을 때 λ 가 나오면 nullable

- 모든 nullable 변수를 구하고 → 해당 변수를 포함하는 프로덕션들에 대해 λ 가 되는 모든 combination을 적용한 production을 추가 → 기존의 λ-production 제거

 

3. unit-production 제거

- 자기 자신에 대한 unit-production 제거 → non unit-production을 P^에 추가 → 모든 (A→*B) 꼴에 대해, B에 대한 non unit-production을 A가 produce 하도록 production 추가

 

---

 

그러면 이렇게 정리한 3가지 불필요한 production 제거 방법을 어떻게 조합해야 CFG를 완벽하게 단순화 할 수 있을까?

이는 다음의 명제를 생각하면 그 제거 순서를 유추할 수 있다.

 

1. λ-production을 제거하면, unit-production 이 생길 수 있다.

2. unit-production을 제거하는 것은 λ-production을 만들지 않는다.

 

따라서 λ-production을 제거한 후에 unit-production을 제거하는 것이 좋다.

 

3. useless-production을 제거하는 것은 λ-production, unit-production 모두 만들지 않는다.

 

위 3가지 명제를 조합하면

 

1. λ-production 제거

2. unit-production 제거

3. useless-production 제거

 

순으로 처리하면 한번에 깔끔하게 CFG를 단순화 할 수 있다.