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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
Тогда <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.  
|statement=
+
|author=Автор теоремы (необязательно)
 +
|about=О чем теорема (необязательно)
 +
|statement=Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся детерменированным конечным автоматом <tex dpi="150">A</tex>.
 +
 
 
|proof=доказательство (необязательно)
 
|proof=доказательство (необязательно)
 
}}
 
}}

Версия 20:37, 20 мая 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]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]