Теорема о детерминизации: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
[[Категория: Теория автоматов]] | [[Категория: Теория автоматов]] | ||
Текущая версия от 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.