Город: Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Воскресенье, 11 октября 2009, 13:00–14:35
Где: ПОМИ РАН

Описание

Незамкнутость бесконтекстных языков относительно пересечения и объединения. Неразрешимость пустоты пересечения бесконтекстных грамматик. Конъюнктивные грамматики, определение через языковые уравнения и через перезапись. Примеры конъюнктивных грамматик для языков \(\{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.