| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Рабочий семинар по математической логике
|
|||
|
|
|||
|
О свойствах звёздной высоты регулярных языков Ю. Д. Теляковская Факультет компьютерных наук, Национальный исследовательский университет «Высшая школа экономики» |
|||
|
Аннотация: Звёздная высота регулярного выражения — минимальное число вложенных операций звездочки Клини, необходимое для записи этого языка регулярным выражением. Известно, что для любого натурального числа существует регулярный язык такой звёздной высоты. Однако при добавлении к используемым для записи регулярных выражений операциям (конкатенации, объединению и звездочке Клини) дополнения ситуация меняется: неизвестно ни одного регулярного языка, при записи которого выражением с дополнением звёздная высота окажется больше 1. В докладе я планирую рассмотреть некоторые примеры влияния на звёздную высоту языков добавления к алфавиту регулярных выражений различных операций, а так же связь звёздной высоты языка со свойствами конечных автоматов, задающих данный язык. |
|||