Участник:Wasteed — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Производящие функции для регулярных языков)
м
 
(не показано 29 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 +
|id=def1.
 +
|neat = 1
 
|definition=
 
|definition=
<tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex><tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{z_{1}}\}</tex> {{---}} множества из различных объектов. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{l}\}</tex> {{---}} количество объектов веса от <tex dpi="130">1</tex> до <tex dpi="130">l</tex> из <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{l}\}</tex> {{---}} соответственно для <tex dpi="130">B</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'').
 +
}}
 +
{{Теорема
 +
|id=th1.
 +
 
 +
|about=Производящая функция регулярного языка
 +
|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</tex> размера $n$ со стартовым состоянием $s$. <tex dpi="150">T \subset Q</tex> {{---}} множество терминальных состояний автомата. Рассмотрим следующие вектора длины <tex dpi="150">n</tex>: вектор <tex dpi="150">\vec{u} = (0, \dots, 0, 1, 0, \dots, 0)^T</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex> и вектор <tex dpi="150">\vec{v}</tex>, у которого единицы стоят на позициях, соответствующих номерам состояний множества <tex dpi="150">T</tex>. <tex dpi="150">D = (d_{ij})</tex> {{---}} матрица переходов автомата <tex dpi="150">A</tex>, где <tex dpi="150">d_{ij}</tex> {{---}} количество символов, которые переводят автомат из состояния <tex dpi="150">i</tex> в состояние <tex dpi="150">j</tex>. Тогда производящая функция для количества слов над языком $L$ равна <tex dpi="150">L(t) = \vec{u}^T (I - tD)^{-1}\vec{v}</tex>.
 +
 
 +
|proof=доказательство (необязательно)
 
}}
 
}}

Текущая версия на 02:59, 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[/math] размера $n$ со стартовым состоянием $s$. [math]T \subset Q[/math] — множество терминальных состояний автомата. Рассмотрим следующие вектора длины [math]n[/math]: вектор [math]\vec{u} = (0, \dots, 0, 1, 0, \dots, 0)^T[/math], содержащий единственную единицу на позиции [math]s[/math] и вектор [math]\vec{v}[/math], у которого единицы стоят на позициях, соответствующих номерам состояний множества [math]T[/math]. [math]D = (d_{ij})[/math] — матрица переходов автомата [math]A[/math], где [math]d_{ij}[/math] — количество символов, которые переводят автомат из состояния [math]i[/math] в состояние [math]j[/math]. Тогда производящая функция для количества слов над языком $L$ равна [math]L(t) = \vec{u}^T (I - tD)^{-1}\vec{v}[/math].
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]