http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=81.9.126.181&feedformat=atom
Викиконспекты - Вклад участника [ru]
2024-03-28T12:20:08Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80895
Участник:Wasteed
2021-05-20T23:51:41Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=Производящая функция регулярного языка<br />
|statement=<br />
Пусть <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>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80894
Участник:Wasteed
2021-05-20T23:50:21Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80893
Участник:Wasteed
2021-05-20T23:49:51Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80892
Участник:Wasteed
2021-05-20T23:49:13Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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">j</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vec{u}(I - tD)^{-1}\vec{v}</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80891
Участник:Wasteed
2021-05-20T23:46:48Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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">j</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vec(U)(I - tD)^{-1}\vec(v)</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80890
Участник:Wasteed
2021-05-20T23:46:11Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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">j</tex> в состояние <tex dpi="150">j</tex>. Тогда утверждается, что <tex dpi="150">L(t) = \vect(U)(I - tD)^{-1}\vect(v)</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80889
Участник:Wasteed
2021-05-20T23:43:30Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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">j</tex> в состояние <tex dpi="150">j</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80888
Участник:Wasteed
2021-05-20T23:36:37Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <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">u = (0, 0,...1, 0,...0)</tex> длины <tex dpi="150">n</tex>, содержащий единственную единицу на позиции <tex dpi="150">s</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80887
Участник:Wasteed
2021-05-20T23:30:05Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t) = a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. Пусть множество состояний <tex dpi="150">A</tex> {{---}} <tex dpi="150">Q; |Q| = n, s \in Q</tex> {{---}} стартовое состояние, <tex dpi="150">T \subset Q</tex> {{---}} множество терминальных состояний. <br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80886
Участник:Wasteed
2021-05-20T23:25:55Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t)=a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>. Пусть множество состояний <tex dpi="150">A {{---}} Q</tex><br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Wasteed&diff=80885
Участник:Wasteed
2021-05-20T23:24:37Z
<p>81.9.126.181: </p>
<hr />
<div>{{Определение<br />
|id=def1. <br />
|neat = 1<br />
|definition=<br />
Пусть <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>. <br />
Тогда <tex dpi="150">L(t)=a_0 + a_1t + a_2t^2 + ... </tex> — это '''производящая функция для регулярного языка''' <tex dpi="150">L</tex> (англ. ''generating function of a regular language'').<br />
}}<br />
{{Теорема<br />
|id=th1. <br />
<br />
|about=(Производящая функция регулярного языка)<br />
|statement=<br />
Пусть <tex dpi="150">L</tex> {{---}} регулярный язык над алфавитом <tex dpi="150">\Sigma</tex>, распознающийся [[Детерминированные конечные автоматы | детерминированным конечным автоматом]] <tex dpi="150">A</tex>.<br />
<br />
|proof=доказательство (необязательно)<br />
}}</div>
81.9.126.181