#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар «Теория доказательств» / Logic Online Seminar (https://www.mathnet.ru/conf876),
28.10.2024, 16:00, ауд. 313 МИАН + Zoom
onsite talk, in Russian | очный доклад на русском языке

Максим Вишникин (МГУ, аспирант, https://www.mathnet.ru/person179526)
Выразительная сила категориальных грамматик с однозначным присвоением категорий

Категориальная грамматика – это классический формализм для описания формальных языков. Идея заключается в том, чтобы каждому символу присвоить одну или несколько категорий, и слово принадлежит языку порождающей грамматикой, если после замены каждого символа одной из своих категорий полученная последовательность сводится к некоторой целевой.

В данном докладе рассматривается подкласс категориальных грамматик, в которых каждому символу присвоена единственная категория. Это ограничение снижает выразительную мощность формализма (например, язык a^+ не может быть порожден). Главная цель – глубже понять, сколько выразительной мощности остается. Можно заметить, что даже если каждому символу назначена уникальная категория, это не означает полное отсутствие неоднозначности; последовательность категорий может иметь разные свертки, потому что все еще существует выбор, откуда в последовательности начать сокращение. Это наблюдение используется для доказательства того, что возможно закодировать любую контекстно-свободную грамматику в категориальную грамматику с единственным назначением категорий таким образом, чтобы слово w принадлежало языку контекстно-свободной грамматики тогда и только тогда, когда его кодирование находится в языке категориальной грамматики. Таким образом, в частности, получается усиление классической теоремы Грейбах о самом трудном языке.

Доклад основан на совместной работе с А.С. Охотиным.

🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&


➰ ВК