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

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

Cтраница 2


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

Пусть А ( 0, X, а0, F, R) - абстрактный детерминированный автомат.  [17]

Теорема 5.8. Класс языков, воспринимаемых-конечными недетерминированными автоматами, совпадает с классом языков, воспринимаемых конечными детерминированными автоматами.  [18]

Теорема 5.11. Пусть А ( 01, X, а0, F, R) - абстрактный детерминированный автомат с конечным множеством заключительных состояний, причем ни одно состояние из F не может вызывать е-переходы.  [19]

Приведенное выше доказательство справедливо не только в случае трехленточной машины Тьюринга, но может быть применено к детерминированным автоматам любого рода, конечным или бесконечным, при единственном условии, что временная память достаточно велика для хранения истории. Существуют и одноленточные обратимые машины, но их частое переключение между рабочей областью ленты и областью записи истории требует большого количества шагов, примерно г / 2, для моделирования г / - шагового обратимого вычисления. Если S - универсальная машина Тьюринга, то R становится машиной для обратимого выполнения любой компьютерной программы.  [20]

Как видно из доказательства, предлагаемый способ детерминизации может дать скачок от п состояний исходного недетерминированного автомата до 2 состояний результирующего детерминированного автомата. Рабином в 1967 г. Ответ был получен только в 1972 г. А.  [21]

Используя такой способ задания вероятностных автоматов, можно ввести теоретико-множественные операции объединения и пересечения вероятностных автоматов по аналогии с операциями над детерминированными автоматами, накладывая, правда, некоторые ограничения на множество стохастических матриц, которые делают довольно узким класс вероятностных автоматов, к которым применимы данные операции. При этом выводы, полученные для теоретико-множественных операций над детерминированными автоматами, справедливы для операций над вероятностными автоматами, разумеется, при сохранении накладываемых органичений на стохастические матрицы. Поэтому, не останавливаясь на этих операциях, перейдем сразу к алгебраическим операциям умножения, суммирования и суперпозиции, которые применимы к произвольным вероятностным автоматам.  [22]

В том случае, когда вероятностные автоматы рассматриваются с точки зрения представления событий подобно тому, как это имеет место в случае детерминированных автоматов, при задании вероятностного автомата А указывается множество Q Q отмеченных состояний.  [23]

В заключение главы отметим, что с содержательной точки зрения операции над вероятностными автоматами означают то же, что и в случае детерминированных автоматов, а свойства, которыми они обладают, повторяют свойства операций над детерминированными автоматами.  [24]

Четкие различия, которые я всегда проводил между детерминированными и вероятностными автоматами, в прошлом не раз подвергались публичной критике, основанной на том, что преобразование детерминированного автомата в эквифинальную кибернетическую машину представляет собой простую и непротиворечивую задачу. Первая часть настоящей главы была написана прежде всего с целью дать ответ на эту критику. Я согласен с тем, что можно смоделировать строго автономную вероятностную систему на детерминированной вычислительной машине, решить на ней операционные задачи, связанные с методом Монте-Карло, и даже эффективно имитировать кибернетический механизм. Но, по моему мнению, утверждать, что такая вычислительная машина может быть преобразована в кибернетическую при помощи искусного программирования по применяемым до сих пор методам, - значит извращать природу кибернетической системы. Не только эта глава, но и вся книга опровергают такую точку зрения.  [25]

В заключение главы отметим, что с содержательной точки зрения операции над вероятностными автоматами означают то же, что и в случае детерминированных автоматов, а свойства, которыми они обладают, повторяют свойства операций над детерминированными автоматами.  [26]

В детерминированном автомате функция переходов F: SB Q - - Q, и функция выходов G: SSy Q - t / являются всюду определенными ( однозначными) функциями.  [27]

Эта замечательная теорема М. Л. Цетлина не полна в двух отношениях. Во-первых, она доказана только для детерминированного автомата, и действительно, в случае стохастического автомата можно обучаться за счет изменения самой вероятности переходов. В литературе показано, что в некоторых примерах такой автомат будет относиться к классу асимптотически оптимальных, хотя у него может не быть глубокого состояния.  [28]

Используя такой способ задания вероятностных автоматов, можно ввести теоретико-множественные операции объединения и пересечения вероятностных автоматов по аналогии с операциями над детерминированными автоматами, накладывая, правда, некоторые ограничения на множество стохастических матриц, которые делают довольно узким класс вероятностных автоматов, к которым применимы данные операции. При этом выводы, полученные для теоретико-множественных операций над детерминированными автоматами, справедливы для операций над вероятностными автоматами, разумеется, при сохранении накладываемых органичений на стохастические матрицы. Поэтому, не останавливаясь на этих операциях, перейдем сразу к алгебраическим операциям умножения, суммирования и суперпозиции, которые применимы к произвольным вероятностным автоматам.  [29]

Седьмая глава посвящена рекурсии по управлению. Рассматриваются контекстно-свободные языки и автоматы с магазинной памятью, моделирование за линейное время детерминированных автоматов с магазинной памятью и с двусторонними операторами чтения, управляемый синтаксический анализ. Доказывается разрешимость проблемы эквивалентности в классе детерминированных управляемых синтаксических анализаторов с просмотром на один символ вперед.  [30]



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