объявление о докладе А. Охотина в среду
Alexander S. Kulikov
"Отрицание в формальных грамматиках"
(среда, 14 октября 2009 г., 11:15)
СПбГУ, 10-я линия Васильевского острова, д. 33 (географический ф-т), ауд. 66.
Известно, что единственное логическое действие, выразимое в
бесконтекстных грамматиках --- это дизъюнкция. Лекция будет посвящена
булевым грамматикам --- обобщению бесконтекстных грамматик, в котором
явным образом задаются также конъюнкция и отрицание. Наличие отрицания
требует более трудоёмкого подхода к определению грамматик. В лекции
будет представлено наиболее общее определение булевых грамматик в
терминах трёхзначной логики, а также дан обзор основных свойств этих
грамматик, в том числе алгоритмов синтаксического разбора.
Лекция примыкает к курсу <<Формальные языки и синтаксический анализ>>,
читаемому в Computer Science клубе 10--11 и 17--18 октября. Слушатели
основного курса могут зайти и на эту лекцию, чтобы узнать
математическое более стройное определение булевых грамматик (в лекции
17 октября в клубе будет дано другое, более простое определение).