Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 446

процесс", можно определить еще одно, заключительное состояние, с выхо­дом из которого будет ассоциировано это действие (один раз!). Понятно, что это состояние будет иметь нестандартный переход.

Представленный метод выявления состояний конечного автомата годит­ся для не очень больших задач, когда строящийся граф остается обозримым. Он может быть улучшен, если в ходе анализа задачи заранее удается выявить содержательно обособленные состояния и переходы между ними. Так, для данной задачи вполне очевидно, что обрабатывающая программа должна работать поразному, когда слово еще не началось и когда уже прочита­ны его первые символы. Иными словами, вычислительный процесс может находиться в двух состояниях: ожидание начала слова (811) и ожидание окончания слова (812). Для каждого из них можно указать набор действий, ассоциированных с переходами, которые явно зависят от содержательного смысла состояний.

Содержательное выделение состояний удобно. В частности, можно се­бе позволить строить недетерминированный конечный автомат, т. е. такой, у которого есть состояния с разными переходами, определяемыми одним и тем же условием. Абстрактная точка зрения на такую ситуацию состоит в том, что при вычислениях выбирается любой из переходов. Недетер­минированный конечный автомат может быть автоматически преобразован в детерминированный, при этом появляются новые состояния, которые не влияют на логическое представление алгоритма.

10.2.3. Табличное представление графа состояний конечного автома­та

Графическое или иное представление графа состояний конечного авто­мата, явно отражающее наименования состояний, условия переходов между состояниями и ассоциированные с ними действия, называют диаграммой переходов. Это определение подчеркивает характерные особенности алго­ритмической природы конечного автомата, вычисления которого сводятся к алгоритму перемещения по графу состояний от одного состояния к другому с выполнением ассоциированных действий.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама