City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 4
Formal Languages

What: Lecture
When: Sunday, 11 October 2009, 13:00–14:35
Where: ПОМИ РАН

Description

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