TransformationalGrammar에서 ChomskyHierarchy 중 Type 3 grammar

처음에는 copy language 는 palindrome language 더 보다 복잡하게 보이지 않으나, copy language 는 ContextFreeGrammar 가 아니다. 일반적으로 copy language 는 ContextSensitiveGrammar를 필요로 한다. ContextSensitiveGrammar를 Parsing 하는 general 한 polynomial-time algorithms 은 존재하지 않는 것으로 알려져있다. 이것은 ContextSensitiveGrammar 의 practical 한 적용에 있어서의 심각한 문제점이다.

※ NP problems and 'intracability' ※ ( polynomial : / exponential : )

※ UnrestrictedGrammar and TuringMachine UnrestrictedGrammar 는 production rule 의 왼쪽과 오른쪽이 어떠한 symbol 의 조합도 될 수 있는 변형문법이다. 해당하는 Parsing automaton 은 TuringMachine 이다. UnrestrictedGrammar 로서 나타내어질 수 있는 많은 문제들은 optimisation problem 으로 대신 나타내어질 수 있고 'Parsing' 은 직접적이지 않은 SimulatedAnnealing 에 의해서 수행된다.