What: | Lecture |
When: | Sunday, 11 October 2009, 13:00–14:35 |
Where: | ПОМИ РАН |
Незамкнутость бесконтекстных языков относительно пересечения и объединения. Неразрешимость пустоты пересечения бесконтекстных грамматик. Конъюнктивные грамматики, определение через языковые уравнения и через перезапись. Примеры конъюнктивных грамматик для языков \(\{a^n b^n c^n \mid n \geqslant 0\}\), \(\{wcw \mid w \in \{a,b\}^*\}\) и \(\{a^{4^n} \mid n \geqslant 0\}\).
A. Okhotin, “Conjunctive grammars”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519--535. А. Охотин, “Конъюнктивные грамматики и системы языковых уравнений”, Программирование, 28:5 (2002), 3--11.