Участник:Wasteed — различия между версиями
Wasteed (обсуждение | вклад) |
|||
(не показано 10 промежуточных версий этого же участника) | |||
Строка 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''). |
}} | }} | ||
{{Теорема | {{Теорема | ||
|id=th1. | |id=th1. | ||
− | |about= | + | |about=Производящая функция регулярного языка |
|statement= | |statement= | ||
− | Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</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">n</tex>: <tex dpi="150">\vec{u} = (0, 0,...1, 0,...0)</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и <tex dpi="150">\vec{v} = (1, 0,...1, 0,...1)^T</tex>, у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. Матрица переходов автомата <tex dpi="150">A</tex>: <tex dpi="150">D = (d_{ij})</tex>, где <tex dpi="150">d_{ij}</tex> {{---}} количество символов, которые переводят автомат из состояния <tex dpi="150">i</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vec{u} (I - tD)^{-1}\vec{v}</tex>. |
|proof=доказательство (необязательно) | |proof=доказательство (необязательно) | ||
}} | }} |
Версия 02:51, 21 мая 2021
Определение:
Пусть
— некоторый регулярный язык, — количество слов длины в языке .
Тогда — это производящая функция для регулярного языка (англ. generating function of a regular language).Теорема (Производящая функция регулярного языка): |
Пусть детерминированным конечным автоматом , — множество состояний — стартовое состояние, — множество терминальных состояний. Рассмотрим такие вектора длины : , содержащий единственную единицу на позиции и , у которого единицы стоят на позициях, соответствующих номерам состояний множества . Матрица переходов автомата : , где — количество символов, которые переводят автомат из состояния в состояние . Тогда утверждается, что . — регулярный язык над алфавитом , распознающийся |
Доказательство: |
доказательство (необязательно) |