 | Александр Охотин (СПбГУ) "Две задачи об отрицании в автоматах и грамматиках" |
|
Коллоквиум лаборатории Чебышева
Четверг 22 декабря 17:15 ауд. 14 (14-я линия В. О., 29)
Александр Охотин (СПбГУ)
"Две задачи об отрицании в автоматах и грамматиках"
Автомат --- это простейшая математическая модель вычисления, а формальная грамматика --- математическая модель синтаксиса языков. В докладе будут представлены две открытых задачи, общая постановка которых одинакова: <<Для некоторой формальной модели, можно ли выразить отрицание в этой модели?>> В одном случае речь пойдёт об *однозначных конечных автоматах* (UFA) --- недетерминированных автоматах с дополнительным ограничением, что для всякой входной строки есть не более одного принимающего вычисления. Ставится такой вопрос: если некоторое множество распознаётся UFA с n состояниями, то сколько состояний может потребоваться, чтобы распознать дополнение этого множества? Вторая задача относится к *конъюнктивным грамматикам* --- расширению обыкновенных формальных грамматик (<<бесконтекстных>>) в правилах которых разрешено использовать операцию конъюнкции. Задача такова: верно ли, что если некоторое множество задаётся грамматикой из этого класса, то и для его дополнения также существует конъюнктивная грамматика?
Приглашаются все желающие! |