4624
правки
Теорема о детерминизации: различия между версиями
Материал из WikiGrapp
Теорема о детерминизации (посмотреть исходный код)
Версия от 11:40, 19 сентября 2011
, 19 сентября 2011нет описания правки
KEV (обсуждение | вклад) м (Защищена страница «Теорема о детерминизации»: чрезмерный спам ([edit=sysop] (бессрочно) [move=sysop] (бессрочно)) [каскадная]) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 1: | Строка 1: | ||
'''Теорема о детерминизации''' ([[Determinization theorem | '''Теорема о детерминизации''' (''[[Determinization theorem]]'') — говорит о том, что если <math>L=L(M)</math> для некоторого недетерминированного [[конечный автомат|''конечного автомата'']] <math>M</math>, то <math>L=L(M')</math> для некоторого [[полностью определенный конечный автомат|''полностью определенного конечного автомата'']] <math>M'</math>, который строится по <math>M</math> по единому [[алгоритм|''алгоритму'']]. | ||
говорит о том, что если <math>L=L(M)</math> для | |||
некоторого недетерминированного [[конечный автомат|''конечного автомата'']] <math>M</math>, то | |||
<math>L=L(M')</math> для некоторого [[полностью определенный конечный автомат|''полностью определенного конечного | |||
автомата'']] <math>M'</math>, который строится по <math>M</math> по единому [[алгоритм|''алгоритму'']]. | |||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2. | |||
[ | * Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | ||
[[Категория: Теория автоматов]] | |||
