Исследовательская группа

Лаборатория языковых инструментов

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

October 10

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

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