|
|
Семинар С. Л. Кузнецова и С. О. Сперанского "Вероятностные и субструктурные логические системы"
9 октября 2025 г. 16:00–17:30, г. Москва, МИАН, комн. 530 (ул. Губкина, 8)
|
 |
|
 |
|
|
|
О свойствах звёздной высоты регулярных языков
Ю.Д. Теляковская
Факультет компьютерных наук, Национальный исследовательский университет «Высшая школа экономики»
|
|
Аннотация:
Звёздная высота регулярного выражения — минимальное число вложенных операций звезды Клини, необходимое для записи этого языка регулярным выражением. Известно, что для любого натурального числа существует регулярный язык такой звёздной высоты. Однако при добавлении к используемым для записи регулярных выражений операций (конкатенации, объединению и звезде Клини) дополнения ситуация меняется: неизвестно ни одного регулярного языка, при записи которого выражением с дополнением звёздная высота окажется больше 1.
В докладе я планирую рассмотреть некоторые примеры влияния на звёздную высоту языков добавления к алфавиту регулярных выражений различных операций, а так же связь звёздной высоты языка со свойствами конечных автоматов, задающих данный язык.
|
|
Обратная связь: