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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Теорема о детерминизации''' (''Determinization theorem'') - говорит о том,...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии 2 участников)
Строка 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.


[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.
 
 
[[Категория: Теория автоматов]]

Текущая версия от 11:40, 19 сентября 2011

Теорема о детерминизации (Determinization theorem) — говорит о том, что если [math]\displaystyle{ L=L(M) }[/math] для некоторого недетерминированного конечного автомата [math]\displaystyle{ M }[/math], то [math]\displaystyle{ L=L(M') }[/math] для некоторого полностью определенного конечного автомата [math]\displaystyle{ M' }[/math], который строится по [math]\displaystyle{ M }[/math] по единому алгоритму.

Литература

  • Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.