B1:기초 Basement
단일 생성규칙 (single production) 제거
Author
2006. 12. 3. 10:59
반응형
단일생성규칙(single production, unit production)
오른편이 단 하나의 Non-Terminal로 구성되는 생성규칙을 말한다.
CFG G(VN, VT, P, S)가 어떤 A∈ VN에 대하여 A=(+)=>A형태의 유도과정을 가지지 않을 때, cycle-free라고 하며, 만약 G가 cycle-free이며, ε-free, 그리고 불필요한 기호를 가지지 않으면 그 문법은 proper하다고 한다.
제거방법
오른편에 Non-terminal 기호가 한개만 나오는 생성규칙을 찾아서, 그 자리를 다른 생성규칙들로 대체함으로써 제거한다.
반응형