Участник:Wasteed — различия между версиями
Wasteed (обсуждение | вклад) |
Wasteed (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
|neat = 1 | |neat = 1 | ||
|definition= | |definition= | ||
| − | Пусть <tex dpi="150">L</tex> {{---}} некоторый регулярный язык, <tex dpi="150">a_n = |L \cap \Sigma^n|</tex> {{---}} количество слов длины <tex>n</tex> в языке <tex>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>L(t)=a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex>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''). |
}} | }} | ||
| − | {{Теорема | + | |
| + | {{Теорема (Производящая функция регулярного языка) | ||
|id=th1. | |id=th1. | ||
| − | |statement= | + | |statement= |
| + | Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся детерменированным конечным автоматом <tex dpi="150">A</tex>. | ||
|proof=доказательство (необязательно) | |proof=доказательство (необязательно) | ||
}} | }} | ||
Версия 20:35, 20 мая 2021
Определение:
Пусть — некоторый регулярный язык, — количество слов длины в языке .
Тогда — это производящая функция для регулярного языка (англ. generating function of a regular language).
