What: | Lecture |
When: | Saturday, 15 October 2011, 19:05–20:40 |
Where: | ПОМИ РАН |
Slides: | combinatoricsonwords_lecture_151011.pdf |
Предположим, конечный автомат получает на вход $ k $-ичное разложение числа $ n $ и выдает символ $ w_n $. Последовательность символов $ w_0w_1w_2\dots $ называется $ k $-автоматным словом. Каковы свойства таких слов? Как еще их можно охарактеризовать? Какие их свойства могут быть проверены конечными автоматами, полученными из исходного — вот, скажем, относится ли к ним избегание паттернов из предыдущей лекции?