Рассматривается класс канонических разделенных грамматик, способных порождать те же языки, что и разделенные грамматики общего вида. Приводятся основные свойства и два характеристических признака канонических грамматик. Предлагается метод унификации нетерминальных символов и доказывается единственность канонического представления разделенной грамматики.

В связи с теоремой 1 возникает вопрос о существовании разделенных грамматик, для которых из L(G;φ) ⊇ L(G;ψ) следует φ ⇒^* ψ. Далее, в формулировках теорем 1 и 4 условие A6 может быть ослаблено, а именно, достаточно предположить, что L0 является производным языком заданной QCS-грамматики. И наконец, как следует из теорем 3 и 4, наиболее сложные для проверки условия A5 и A6 можно изменять по отдельности, но не одновременно (см. грамматику g-c-крышкой); вопрос о дополнительном условии, гарантирующем совместно с B5 и B6 каноничность QCS-грамматик, остается открытым.
 

1. Courcelle B. Une forme canonique pour les grammaires simples deterministes // RAIRO - Theoretical Informatics and Applications. 8.R1. 1974. P. 19-36.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. М.: Мир, 1978.
3. Серебряков В.А., Соловьев С.Ю. Задача совместимости свойств формальных грамматик // Информационные процессы. 2012. 12. No.4. С. 408-437.
4. Bastien C., Czyzowicz J., Fraczak W., Rytter W. Prime normal form and equivalence of simple grammars // Implementation and Application of Automata. Lecture Notes in Computer Science. 3845. Berlin: Springer, 2006. P. 78-89.
5. Paull M.C., Unger S.H. Structural equivalence of context-free grammars // J. Computer and System Sci. 1968. 2. P. 427-463.

---

Class canonical separated grammars that generate the same language as the general separated grammar are considered. We present the basic properties and two criterion of canonical grammars. We propose a method of nonterminals unication and prove the uniqueness of the canonical representation separated grammar.