Аноним

Теорема о детерминизации: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Теорема о детерминизации''' ([[Determinization theorem|''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.


[Касьянов/95]


[[Категория: Теория автоматов]]
[[Категория: Теория автоматов]]