Участник:Wasteed — различия между версиями
| Строка 11: | Строка 11: | ||
|about=(Производящая функция регулярного языка) | |about=(Производящая функция регулярного языка) | ||
|statement= | |statement= | ||
| − | Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. Пусть | + | Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. Пусть <tex dpi="150">Q</tex> {{---}} множество состояний <tex dpi="150">A, |Q| = n, s \in Q</tex> {{---}} стартовое состояние, <tex dpi="150">T \subset Q</tex> {{---}} множество терминальных состояний. Рассмотрим вектор <tex dpi="150">u = (0, 0,...1, 0,...0)</tex> длины <tex dpi="150">n</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex>. |
|proof=доказательство (необязательно) | |proof=доказательство (необязательно) | ||
}} | }} | ||
Версия 02:36, 21 мая 2021
Определение:
Пусть — некоторый регулярный язык, — количество слов длины в языке .
Тогда — это производящая функция для регулярного языка (англ. generating function of a regular language).
| Теорема ((Производящая функция регулярного языка)): |
Пусть — регулярный язык над алфавитом , распознающийся детерминированным конечным автоматом . Пусть — множество состояний — стартовое состояние, — множество терминальных состояний. Рассмотрим вектор длины , содержащий единственную единицу на позиции . |
| Доказательство: |
| доказательство (необязательно) |
