#матлог #учёба #спецсеминар

Ближайший семинар «Категориальные грамматики» состоится 28 ноября (28.11.2024).

Начало: 18:30. Аудитория: 424.

Докладчик: Т.Г. Пшеницын
Тема: ''Операции вставки на формальных языках: от простого к сложному''

В данном обзорном докладе будет рассмотрена классическая операция на формальных языках — вставка — и её разновидности. Стандартный вариант этой операции языкам L и M ставит в соответствие множество слов {uyv|uv из L, y из M}. В литературе также изучаются контекстные вставки: например, когда зафиксировано (конечное) множество контекстов C (состоящее из пар слов), и вставка слова возможна только между строками z и t, пара из которых принадлежит C. Есть ещё более хитрая сайт-направленная вставка, которая языкам L и M ставит в соответствие язык {uzytv|uztv из L, zyt из M}; это тоже контекстная вставка, однако контексты z и t здесь определяются не внешним образом, с помощью фиксированного множества C, а внутренним.

Контекстные вставки изначально мотивировались лингвистическими приложениями (например, в работе Галюкшова "Полуконтекстные грамматики" 1981 года), а позднее — приложениями в биоинформатике: если рассматривать молекулы ДНК как слова, то их взаимодействие действительно можно моделировать контекстной вставкой.

В докладе будет рассказано об избранных свойствах вставок. В частности, планируется показать конструкцию полуконтекстной грамматики Галюкшова, порождающей язык, не являющийся контекстно-свободным (и даже полулинейным). В конце доклада предполагается описать текущую работу автора в данном направлении и один из результатов: существует конечный язык, замыкание которого относительно сайт-направленной вставки не является контекстно-свободным.

➰ ВК