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