[오토마타] 14. CFG & Derivation

Leftmost / Rightmost Derivation

다시 복습해보면 Derivation(유도)는 문법으로부터 문장을 만드는 과정에 등장하는 Sentential Form 또는 Sentence를 말한다.

이때 어떤 프로덕션이 S → ABC 이고, A, B, C 는 변수라고 해보자.

A, B, C가 produce하는 결과물을 각각 a, b, c 라고 할 때, S에서 시작해서 문장을 만드는 과정의 선택지는 여러가지가 있을 수 있다.

 

S => aBC => abC => abc 가 될 수도 있고,

S => AbC => Abc => abc 가 될 수도 있다.

 

따라서 같은 문장을 유도하는 과정이 여러가지 인 경우에는 각 단계에서 어떤 것을 선택해야 할 지 고려해야 할 점이 많다보니 상대적으로 비효율적이라, 일관된 기준을 가지고 유도할 수 있는 방법을 고안했고, 그 방법들이 바로 leftmost derivation, rightmost derivation 이다.

(어떻게 유도하든 같은 결과를 내는데, 굳이 이것저것 고려할 필요가 있냐는 것)

 

이름에서 유추할 수 있듯, leftmost derivation은 2개 이상의 변수를 만났을 때, 왼쪽에 있는 변수부터 대체하는 것이고, rightmost derivation은 오른쪽에 위치한 변수부터 대체하는 것을 말한다.

 

 

Example

 

위 문법은 화살표 왼쪽의 변수가 1개이므로 CFG이다. (Linear하지 않으니 RG도 아니다.)

이 문법에 대해 leftmost drivation으로 abbbb를 유도해보면 아래와 같다.

 

 

 

S에서 AB 라는 2개의 변수를 유도한 뒤, 왼쪽에 있는 A부터 대체하기 시작한다.

그 이후에 2개의 B가 존재하며, 역시 왼쪽의 B부터 대체한다.

다시 A B가 등장하면 왼쪽의 A를 대체하고, B 2개가 나오면 왼쪽의 B를 대체한다.

 

 

rightmost derivation 방식은 위와 같다.

역시 오른쪽의 변수부터 대체하는 방법으로 문장을 유도한다.

 

 

Derivation Tree

지금까지는 유도과정을 => 기호를 사용해 나열했었다.

그런데 문장을 유도하는 과정을 트리 형태로도 표현할 수 있다.

이때 만들어지는 트리를 Derivation Tree 라고 한다.

 

Derivation Tree의 정의는 아래와 같다.

 

어떤 CFG에 대한 Drivation Tree 는 ordered tree 이며, 아래의 속성을 만족한다.

- root 는 S (start variable) 로 표기한다.

- 모든 leaf 는 terminal 또는 λ 로 표기한다. 이때 λ 로 표기된 leaf node는 형제 노드가 없어야 한다.

- 모든 leaf 가 아닌 노드는 variable로 표기한다. (interior vertex)

- variable 로 표기된 노드의 자식이 a1, a2, a3., ... , an 이라면 해당 variable는 a1 a2 a3 ... an 을 produce한다.

 

이때 ordered tree 는 자식 노드가 배치된 순서를 고려하여, 그 순서가 다르면 다른 트리로 생각한다.

 

말보다는 예시를 보는 것이 더 좋다.

 

 

위와 같은 문법이 있고, w = abbbb 가 주어질 때, 이 문장을 유도하는 derivation tree 를 그려보면

 

 

root 는 S로 시작하며, S가 aAB를 produce 하므로 그 각각의 요소 a, A, B를 노드로 하는 정점을 자식으로 갖도록 구성한다.

이때 a는 터미널이므로 리프노드이다.

다시 A는 bBb 를 produce 하므로, 그 각각의 요소 b, B, b 를 노드로 하는 정점을 자식으로 갖도록 구성하고, 계속해서 등장하는 변수에 대해 같은 과정을 반복한다.

 

이때 어떤 중간의 변수를 root로 하는 subtree를 잡을 수 있다.

위 그림에서는 맨 아래의 A를 root로 하는 서브트리를 생각할 수 있다.

이 서브트리를 가리켜 partial derivation tree 라고 부르며, partial derivation tree 의 leaf는 V, T, λ 모두 될 수 있다.

 

 

즉, 이렇게 중간만 똑 떼서 보면 이를 partial derivation tree 로 보는 것이다.

이때는 leaf 가 V여도 상관없다.

 

derivation tree를 만들었을 때 λ 를 제외한 모든 leaf node를 왼쪽에서부터 순서대로 읽으면 abbbb 를 읽어낼 수 있다.

이렇게 derivation tree에서 λ를 제외하고 모든 leaf node를 읽어 구성한 문자열을 yeild 라고 하며, 이는 문장과 같다.

 

이와 관련하여 다음과 같은 정리를 얻을 수 있다.

 

1. 만약 CFG로 만드는 언어 L(G) 가 있다면, 이 언어의 문장을 유도하는 Derivation Tree를 그릴 수 있다.

2. 만약 Derivation Tree의 성질 5가지를 만족하는 Tree를 그릴 수 있다면, 이 트리의 yeild는 반드시 문장이다.

(간단히 말하면 문장에 대해서 Derivation Tree를 만들 수 있고, Derivation Tree를 만들었다면 그 yeild는 문장이다.)

 

3. 어떤 partial derivation tree 의 루트가 S 라면, 그 yeild 는 반드시 sentential form 이다.

(partial 이므로 문장은 아닐 수 있다. 너무나도 자명한 정리다.)