TransformationalGrammar에서 ChomskyHierarchy 중 Type 2 grammar

Grammar에서는 nonterminal symbol이 terminal 이나 nonterminal symbol로 변하는데 이 변하는 룰이 context(주위 환경)에 의존하지 않는다고 해서 ContextFreeGrammar라고 불린다. 예를 들어 (B는 항상 a로 변한다고 할때, aBc나 bBd 일 때 각각 aac, bad로 변환되는 것을 의미한다.)

ContextFreeGrammar를 canonical한 방법으로 기술한것을 Chomsky normal form 또는 Greibach normal form 이라고 한다.

Palindrome language 는 ChomskyHierarchy의 다음 level 인 ContextFreeGrammar (CFGs) 로서 다루어진다. ContextFreeGrammar에 대해서 주의깊게 봐야 하는 이유는 RnaStructure 2차 구조가 palindrome language 의 한 종류이기 때문이다.

※ ParseTree ContextFreeGrammar 와 sequence 의 alignment 는 ParseTree 라 불리우는 우아한 representation 으로 나타낼 수 있다. (Figure 9.5)

※ PushDownAutomata CFG 에 대한 Parsing automaton 은 PushDownAutomaton이다.