Редактирование: Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА]] эквивалентный [[Детерминированные конечные автоматы|ДКА]] следующим образом:
 
Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА]] эквивалентный [[Детерминированные конечные автоматы|ДКА]] следующим образом:
 
* Начало.
 
* Начало.
* '''Шаг 1.''' Помещаем в очередь <tex>Q</tex> множество, состоящее только из стартовой вершины.
+
* '''Шаг 1''' Помещаем в очередь <tex>Q</tex> множество, состоящее только из стартовой вершины.
* '''Шаг 2.''' Затем, пока очередь не пуста выполняем следующие действия:
+
* '''Шаг 2''' Затем, пока очередь не пуста выполняем следующие действия:
 
** Достаем из очереди множество, назовем его <tex>q</tex>
 
** Достаем из очереди множество, назовем его <tex>q</tex>
 
** Для всех <tex>c \in \Sigma</tex> посмотрим в какое состояние ведет переход по символу <tex>c</tex> из каждого состояния в <tex>q</tex>. Полученное множество состояний положим в очередь <tex>Q</tex> только если оно не лежало там раньше. Каждое такое множество в итоговом ДКА будет отдельной вершиной, в которую будут вести переходы по соответствующим символам.
 
** Для всех <tex>c \in \Sigma</tex> посмотрим в какое состояние ведет переход по символу <tex>c</tex> из каждого состояния в <tex>q</tex>. Полученное множество состояний положим в очередь <tex>Q</tex> только если оно не лежало там раньше. Каждое такое множество в итоговом ДКА будет отдельной вершиной, в которую будут вести переходы по соответствующим символам.
 
** Если в множестве <tex>q</tex> хотя бы одна из вершин была терминальной в НКА, то соответствующая данному множеству вершина в ДКА также будет терминальной.
 
** Если в множестве <tex>q</tex> хотя бы одна из вершин была терминальной в НКА, то соответствующая данному множеству вершина в ДКА также будет терминальной.
* Конец.
+
* Конец
  
 
== Построение эквивалентного ДКА по НКА ==
 
== Построение эквивалентного ДКА по НКА ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: