Детерминированный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 3
Аксиома Коула: суммарный интеллект планеты - величина постоянная, в то время как население планеты растет. Законы Мерфи (еще...)

Детерминированный автомат

Cтраница 3


Для этого предположим, что компоненты векторов г, Ч) и z являются элементами множества G целых чисел. Если речь идет о детерминированной инвариантной во времени системе со стохастическими входными данными ( детерминированных автоматах со стохастическими входными данными), то для математического ожидания t) ( подразд.  [31]

32 Недетерминированная диаграмма переходов. [32]

Этот автомат недетерминированный, ибо одно из его состояний является таким узлом, из которого выходят две дуги, помеченные одним и тем же входным символом. Если автомат в состоянии q получает слово ( входной символ) этот, то он переходит в состояния 72 и 7з - Как указывалось в § 5.2.3, понятия конечного детерминированного автомата и конечного недетерминированного автомата эквивалентны в том смысле, что оба эти множества автоматов воспринимают регулярные языки. Однако недетерминированные автоматы значительно удобнее при описании языков.  [33]

Описанные выше результаты позволяют построить теорию поведения автоматов ( случайных и детерминированных) в случайных средах. Ограничимся рассмотрением одних лишь автоматов Мура, поскольку в случае автоматов Мили возникает необходимость в некоторых усложнениях теории, делающих ее менее прозрачной. Условимся также рассматривать детерминированные автоматы как частный случай случайных автоматов, что, как уже отмечалось выше, всегда возможно.  [34]

Этот транслятор использует упомянутые выше лексический и синтаксический анализаторы на основе разработанного исходного конечного автомата, который соответствует грамматике Бэкуса-Наура. Итак, конечный детерминированный автомат с магазинной памятью, соответствующий грамматике проблемно-ориентированного языка общения пользователя с ЭВМ на определенном этапе диалога, следует рассматривать в качестве самостоятельной части этого этапа, которая управляет процессом разбора и выполнения сформированного запроса пользователя с помощью универсальных блоков лексического и синтаксического анализов.  [35]

Когда число варьируемых состояний объекта невелико, следует обращаться к альтернативной адаптации, которая позволяет поддерживать в объекте оптимальное состояние. В данной главе рассматриваются два алгоритма альтернатив ной адаптации - детерминированные автоматы с целесообраз ным поведением и стохастические автоматы с переменной струк турой. Эти автоматы применяются для переключения алгорит мов при решении задач адаптивной поисковой оптимизации, адаптивной сортировки массивов, адаптивного выбора способа кодирования при передаче данных по каналу связи и адаптив ного определения длины информационной части пакета в ка нале связи двух ЭВМ.  [36]

Так как регулярные ( распознаваемые конечными автоматами) подмножества S замкнуты относительно, f /, 1 и у то отсюда следует, что Empty ( S) рекурсивно и в действительности примитивно рекурсивно. Легко построить конечный автомат для L ( a) и проверить, допускает ли автомат некоторое слово; для этого существуют хорошо известные процедуры. Априорный анализ такой процедуры, однако, показывает, что из детерминированных автоматов для у-выражений a, p получился бы недетерминированный автомат для а р или у ( а), и тогда пришлось бы применить подмножественную конструкцию Рабина - Скотта, чтобы получить автомат для - l ( tx p) или Пу ( а) - Поскольку под-множественная конструкция может экспоненциально увеличить число состояний в автомате, у-выражения, в которых k дополнений чередуются с у и конкатенациями, могут привести к автомату с th ( 2) состояниями.  [37]

Есть одна несущественная причина: в одном или двух отношениях современная аппаратура принципиально более сложна в обращении, чем старая. Во-первых, появились прерывания ввода-вывода, они происходят непредсказуемо, и моменты их появления невоспроизводимы. По сравнению со старой последовательной машиной, которая по замыслу являлась полностью детерминированным автоматом, такая разница драматична, и седые волосы многих системных программистов свидетельствуют о том, что мы не должны легкомысленно относиться к возникающим при этом логическим проблемам. Во-вторых, современные машины оборудованы многоуровневыми запоминающими устройствами, что заставляет нас думать о стратегии управления, которая, несмотря на обширную литературу на эту тему, остается весьма неясной. Вот, пожалуй, и все, что стоит сказать о структурных новшествах современных машин.  [38]

39 Графы переходов автоматов, допускающие языки, представленные регулярными выражениями ( a P V. ( б Рт. ( e Р. [39]

Необходимо упомянуть один дополнительный результат. Однако детерминированный конечный автомат, эквивалентный данному НКА с п состояниями, может иметь вплоть до 2 состояний. Поэтому переход к детерминированному автомату не всегда дает аффективный способ моделирования недетерминированного конечного автомата.  [40]

41 Начало построения автомата для поиска подстроки hello. [41]

Конечный автомат, настроенный на данный образец, можно использовать для сравнения с образцом; если автомат переходит в принимающее состояние, то это означает, что образец найден в тексте. Использование конечных автоматов очень эффективно, поскольку такой автомат обрабатывает каждый символ однократно. Поэтому поиск образца с помощью конечного автомата требует не более Т сравнений. Теперь встает задача создания конечного детерминированного автомата, отвечающего данной подстроке. Это непросто; существующие алгоритмы работают долго.  [42]

Вообще следует заметить, что во многих частях теоретической кибернетики наблюдается своеобразный параллелизм лапласовского и нелапласовского подходов. Под последним понимается такая трактовка причинной детерминации, которая допускает ее неоднозначность, предста-вимую, в частности, в вероятностно-статистических терминах. При этом нелапласовская трактовка причинности нередко оказывается обобщением лапласовской. Такая ситуация наблюдается, например, в теории автоматов. Вероятностный автомат с содержательной точки зрешш можно считать обобщением понятия детерминированного автомата, в силу чего хорошо известная проблематика абстрактной теории автоматов естественным образом переносится и в теорию вероятностных автоматов ( хотя в последней, конечно, и проблематика, и особенно методология исследований претерпевают существенные изменения) ( Б. А. Трахтенброт, Я. М. Барздинь, 1970, стр. Другим примером может служить теория формальных нервных сетей, развиваемая в духе Мак-Каллока на основе диаграмм Венна.  [43]



Страницы:      1    2    3