Участник: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">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">u = (0, 0,...1, 0,...0)</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и вектор <tex dpi="150">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>.
+
Пусть <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">u = (0, 0,...1, 0,...0)</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и <tex dpi="150">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:50, 21 мая 2021

Определение:
Пусть [math]L[/math] — некоторый регулярный язык, [math]a_n = |L \cap \Sigma^n|[/math] — количество слов длины [math]n[/math] в языке [math]L[/math]. Тогда [math]L(t) = a_0 + a_1t + a_2t^2 + ... [/math] — это производящая функция для регулярного языка [math]L[/math] (англ. generating function of a regular language).
Теорема ((Производящая функция регулярного языка)):
Пусть [math]L[/math] — регулярный язык над алфавитом [math]\Sigma[/math], распознающийся детерминированным конечным автоматом [math]A[/math], [math]Q[/math] — множество состояний [math]A, |Q| = n, s \in Q[/math] — стартовое состояние, [math]T \subset Q[/math] — множество терминальных состояний. Рассмотрим такие вектора длины [math]n[/math]: [math]u = (0, 0,...1, 0,...0)[/math], содержащий единственную единицу на позиции [math]s[/math] и [math]v = (1, 0,...1, 0,...1)^T[/math], у которого единицы стоят на позициях, соответствующих номерам состояний множества [math]T[/math]. Матрица переходов автомата [math]A[/math]: [math]D = (d_{ij})[/math], где [math]d_{ij}[/math] — количество символов, которые переводят автомат из состояния [math]i[/math] в состояние [math]j[/math]. Тогда утверждается, что [math]L(t) = \vec{u} (I - tD)^{-1}\vec{v}[/math].
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]