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

Счетчиковый автомат

Cтраница 1


Счетчиковый автомат состоит из конечного множества счетчиков х - 11 / л, алфавита и программы автомата.  [1]

Счетчиковый автомат порождает ( печатает) слово в алфавите автомата, продвигаясь по программе, меняя значения счетчиков и печатая очередной символ. Движение начинается в начальной вершине. Оператор недетерминированного перехода выбирает произвольным образом направление дальнейшего движения.  [2]

Счетчиковый автомат на рис. 5.2 реализует декодирующую функцию К-1, которая является частично-рекурсивной. Этот автомат имеет два счетчика х и у, он останавливается и печатает слово К 1 ( т), если т является начальным значением счетчика х и одновременно числом-кодом. В противном случае автомат зацикливается.  [3]

Для построения ингибиторной сети, моделирующей счетчиковый автомат, достаточно каждому оператору программы автомата сопоставить моделирующий его фрагмент ингибиторной сети и затем связать эти фрагменты в единую сеть. Переходы, соответствующие операторам печати, помечаются соответствующими символами, остальные переходы вводятся как Л - переходы. Фрагменты связываются в сеть путем слияния одинаково помеченных выходных и входных мест.  [4]

Способ, которым строится помеченная ин-гибиторная сеть, моделирующая счетчиковый автомат, непосредственно убеждает в эквивалентности терминальных языков, порождаемых обеими системами, если для сети фиксировать терминальный язык с такой резмет-кой Mf, при которой все места сети, кроме места, соответствующего оператору стоп, имеют нулевую разметку, а это место - единичную. Таким образом, класс Со ( /) всех терминальных языков ( помеченных) ингиби-торных сетей является классом рекурсивно перечислимых языков. Класс СЛ ( /) образован префиксами языков из класса JCo ( /) рекурсивно перечислимых языков и поэтому он также является классом рекурсивно перечислимых языков.  [5]

Теорема 5.1. Любой рекурсивно перечислимый язык может быть порожден некоторым счетчиковым автоматом.  [6]

Достаточно продемонстрировать, как в иерархических сетях можно промоделировать оператор условного вычитания единицы счетчикового автомата.  [7]

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

Чтобы убедиться в этом, достаточно показать неразрешимость более узкой проблемы, а именно - не существует алгоритма, который для любого счетчика может установить, будет ли его начальное нулевое значение изменено хотя бы один раз, т.е. является ли счетчик 0-ограниченным или нет. Введем дополнительный вспомогательный счетчик х, запись в который делается только после того, как исходный автомат останавливается, выполнив заключительный оператор стоп. Для этого достаточно заменить этот оператор на последовательность операторов ж: х 1 и стоп. Если бы была разрешима проблема 0-ограниченности, то мы могли бы решать проблему остановки счетчикового автомата, воспользовавшись описанным преобразованием. Таким образом, проблема Оюграниченность не может быть разрешимой и, следовательно, неразрешима более общая проблема ограниченности счетчиков и проблема ограниченности ингибиторной сети.  [9]



Страницы:      1