JetBrains Research — наука, меняющая мир

Семинар по операциям в формальных грамматиках

Правильное понимание формальных грамматик как особой логики для описания синтаксиса языков было достигнуто в 1980-е гг. К сожалению, пока старые учебники продолжают распространять ранний подход Хомского, это понимание остаётся по большей части неизвестным широкой публике. Цель данного доклада --- представить современное понимание грамматик как систем логического вывода, а также как индуктивных определений в логике FO(LFP), и затем обсудить вопрос использования различных операций в правилах грамматик. В обыкновенных грамматиках ("бесконтекстных" по Хомскому), используются две операции: конкатенация строк и логическая дизъюнкция. Эта формальная система может быть расширена добавлением различных новых операций: для некоторых операций, выразительная мощность грамматик остаётся неизменной; введение ряда других операций разрушает модель делая её вычислительно универсальной и потому бессмысленной; наконец, существуют операции, добавление которых позволяет получить осмысленные новые классы формальных грамматик.

Докладчик: Александр Охотин.

10.10.2016, 17:15, Мат-Мех, ауд. 3248.

Место: ауд. 3248, мат-мех. факультет СПбГУ, Старый Петергоф, Университетский пр-т, д. 28