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

Описание

Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство непредставимости языков бесконтекстными грамматиками: лемма накачки, непредставимость языка \( \{a^n b^n c^n \mid n \geqslant 0\} \). Разрешимость задачи пустоты и задачи принадлежности для бесконтекстных грамматик.