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

Cтраница 1

Рассмотрим детерминированный автомат, задающий множество нормальных слов. [1]

Помимо детерминированных автоматов в теории самоорганизующихся систем приходится рассматривать автоматы, имеющие случайные переходы. [2]

Работа детерминированного автомата заключается в том, что когда на вход его подается S, на выходе появляется г, - у ( s) в соответствии с его отображением у к. Если каждый автомат имеет g входов, на каждый из которых могут быть поданы либо ноль либо единица, то всего на вход может быть подано N 2g стимулов. Пусть автомат может выдать / реакций. [3]

Под детерминированным автоматом будем понимать такое звено автоматического управления, составные элементы которого взаимодействуют точно предписанным образом в соответствии с заданным алгоритмом управления. [4]

Если А - детерминированный автомат с магазинной памятью, то множество L ( A) последовательностей, которые в нем представимы, являются бесконтекстным языком без неоднозначности. [5]

Легко видеть, что детерминированный автомат можно рассматривать как частный случай автомата со случайными переходами, у которого для каждого х при любом данном / лишь точно одна из вероятностей pi / ( x) равна единице, а все остальные вероятности равны нулю. [6]

Теорема 5.4. Если А - детерминированный автомат, воспринимающий язык L, и В - минимальный автомат для L, то существует гомоморфизм автомата А на В. [7]

Пусть р - некоторое состояние детерминированного автомата А, в котором он выполняет действие а. Глубиной этого состояния d ( ( р называется минимальная длина последовательности входных сигналов ( наказаний), приводящая автомат к смене действия. Глубиной автомата d ( А ] называется максимальная из глубин его состояний. [8]

В-четвертых, в традиционных конечных детерминированных автоматах с магазинной памятью и соответствующих им грамматиках не отражено содержание семантического анализа предложений языка. Для этой цели следует воспользоваться понятием семантического кода, который может быть приписан при формальном определении правил грамматики символам в виде целого числа. В результате появление в предложении языка, допустимого с точки зрения грамматики терминального символа, может сопровождаться определенным образом закодированными действиями по смысловой проверке этого символа и ( или) выполнению запроса пользователя. Все ненулевые значения семантического кода должны вызывать передачу очередной лексемы ( при необходимости преобразованной к целому или реально-числовому представлению) блоку семантического анализа и реализации запросов пользователя. [9]

Теорема 5.5. Пусть А - конечный детерминированный автомат, имеющий п состояний. Существует алгоритм, требующий О ( / г2) шагов, строящий минимальный автомат, эквивалентный заданному. [10]

Легко проверяется, что любой конечный детерминированный автомат, распознающий язык Lp, требует не менее р состояний. [11]

Реализация перечисленных мер по модернизации конечного детерминированного автомата с магазинной памятью позволяет создать универсальный для всех этапов сценария диалога синтаксический анализатор запросов пользователей. [12]

Для любого конечного недетерминированного автомата можно построить эквивалентный ему конечный детерминированный автомат. [13]

Вероятностные конечные автоматы можно задавать с помощью графоидов так же, как и детерминированные автоматы, учитывая, однако, то обстоятельство, что около каждой дуги графоида, обозначающей переход из состояния 7 ( в 7ft, кроме буквы входного алфавита х Х ставится значение вероятности Pih ( x) этого перехода. В случае актуальных автоматов, для которых вероятности Pik ( x) 0 ( строго положительны), графоиды представляют собой насыщенные мультиграфы, порядок которых определяется числом элементов множества Q, a мультичисло - числом букв входного алфавита X. Естественно, что аналитический способ записи и геометрическая интерпретация графоида неудобны для задания вероятностного автомата даже при сравнительно небольшом числе букв входного альфавита, поэтому вероятностный автомат удобнее задавать системой стохастических матриц в указанной ранее форме. [14]

Схема взаимодействия различных групп проектировщиков. [15]

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