[Automata] Grammar Transforming 방법들

Chapter6의 내용이다!

 

앞서 배운 문맥자유문법 같은 경우, 우변에 오는 형태에 어떠한 제약도 없었다.

그런데 이게 항상 좋기만 한것도 아니다..

따라서 이번 챕터에서는 문법을 단순하게 만드는 방법에 대해서 다뤄보려고 한다. 하지만 단순화 한다고 해서 무조건! 개수가 줄어야 하는 것이 아니라는걸 염두에 두자. 

유용한 치환 규칙

어렵지 않은 규칙이다. 

A->aB

B->c라면

 

A->ac로 바꿀 수 있다는 규칙이다.

 

증명은 생략하겠다. 

필요없는 production 삭제하기

 

먼저 변수가 필요없다와 필요 있다를 구분하는 방법을 알아야 하는데,  (Definition 6.1)

 

필요 있다 : L(G)에 포함되는 w에 대하여, S->xAy->w 으로 만들어질 수 있는 x, y가 (V set T)* 에 대하여 w가 하나라도 있을 때이다. 

필요 없다 : 필요 있지 않은 것.

 

Theorem 6.2

G = (V, T, S, P)가 CFG이다. 그렇다면 G_hat = (V_hat, T_hat, S, P_hat)이고 useless variable이나 productions이 없어야 한다. 

 

Theorem 6.2의 알고리즘은 다음과 같다. 

 

1) V_1을 ∅으로 만든다. 

2) 더이상의 변수가 V_1으로 더해지지 않을 때까지 반복한다. 

V에 속하는 모든 A에 대하여, A가 A->x1x2...xn이고 xi가 V_1 sum T에 속하면 A를 V_1에 추가한다. 

3) 

ƛ-production 삭제하기

어떠한 경우에는 A->ƛ 처럼 우변에 lambda가 오는 것이 불편할 때가 있다. 

 

람다 프로덕션의 정의는 다음과 같다. (Definition 6.2)

 CFG의 어떠한 production이라도 A->ƛ 라면, 람다 프로덕션이다. 

 

어떠한 변수 A에서 ƛ로 파싱하는게 가능하다면 A는 nullable이라고 부른다. 

 

Theorem 6.3 을 통해서 람다 프로덕션을 삭제할 수 있다는것을 증명한다. 

 

Unit-production 삭제하기

A->B

 

중요한 두개의 Normal Form(정규형)

Chomsky Normal Form

모든 production이 

 

A->BC

A->a

 

꼴이어야 한다.

 

A,B,C는 V에 속하고, a는 T에 속해야 한다. 

Greibach Normal Form

모든 production이 A->ax 꼴이고, a는 T에, x는 V*에 속한다.

A-> aAAAA이런것도 가능하다. 

CYK알고리즘