• idea: Useless Productions

$S→ AB, A \to aA | a, B \to AB$

B에서는 terminal을 만들지 못해, 결과적으로 S에서는 아무런 string을 만들지 못한다(language is empty)

→ CFG를 simplification 하여 NO useless productions, NO e-productions, NO-unit-productions 를 달성하자

Substitution Rule

$A→x_1Bx_2, B\to y_1|y_2 ... |y_n$이라고 할 때 새로운 $\hat G = (V,T,S,\hat P)$를 다음과 같이 만들자

$A→x_1y_1x_2|x_1y_2x_2|...| x_1y_nx_2$

then $L(\hat G) = L(G)$

Simplification of CFG

if CFL $L$ does not contain $\epsilon$, there exists CFG $G$ that $L(G) = L$ s.t NO useless productions, NO e-productions, NO unit-productions

즉 저 3가지를 다 지워도 동일한 L을 생성하는 CFG를 구성할 수 있다.

1. useless symbol을 제거해 버린다. 포함되어 있는 derivation을 전부 제거
2. $A→\epsilon$을 전부 제거한다.
3. $A→B$를 전부 제거한다.

→ 모든 문법은 터미널 하나로 가거나 길이 2 이상이다.

CFG Normal Form: Chomsky Normal Form(CNF)

모든 production이 $A→ BC, A→a$

Generating

1. Simplification 하여 터미널 하나로 가거나 길이 2 이상으로 만든다.