Главная > Разное > Логика, автоматы, алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

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

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

Значительно сложнее обеспечить определенные выходные последовательности при задании входных последовательностей бесконечной длины. Такие случаи часто встречаются на практике, когда заранее нельзя установить длительность работы проектируемого устройства и когда выходы должны индицировать некоторые общие свойства входных последовательностей, начинающихся с первого такта работы машины. В таких случаях возникает основной вопрос: каким образом задать соответствие между бесконечными, входными и выходными последовательностями, так как прямое перечисление последовательностей здесь уже невозможно. Как бы ни было задано это соответствие, оно означает в конечном итоге задание алгоритма, позволяющего установить для каждого такта, каковы входной и выходной символы в этот такт.

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

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

Поэтому при формулировке заданий на автомат (в случае бесконечных последовательностей) используются специальные приемы (или, иначе говоря, специальные языки), обходящие это затруднение. Один из этих приемов — запись задания не с помощью описаний соответствий между входными и выходными последовательностями, а непосредственно с помощью описания регулярных событий, которые автомат должен представлять. Этот прием изложен в § 8.4, где указан и эффективный способ построения основной таблицы автомата и таблицы преобразователя, которые в совокупности образуют П-машину, представляющую заданные события.

Другой значительно менее экономный (по требуемому числу состояний автомата) способ решения этой задачи был описан в § 7.4 в ходе доказательства теорем Клини.

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

Если человек не смог выразить задание на подобном языке, то остается открытым вопрос, произошло ли это потому, что задание не может быть переведено на этот язык и, значит, реализовано П-машиной, либо потому, что человек не сумел «творчески» это сделать.

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

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

Наиболее простой случай имеет место, если множество входных последовательностей никак не ограничено, т. е. если на входе автомата может появиться любая последовательность. В этом случае задача о построении минимальной в указанном смысле П-машины полностью решена, т. е. найдены необходимые и достаточные условия минимизации. Метод, осуществляющий построение минимальной П-машины, связан с разбиением матрицы соединений на определенные подматрицы и указан в § 9.6.

Значительно сложнее обстоит дело тогда, когда множество возможных входных последовательностей как-либо ограничено. Если предположить, что эти ограничения произвольны, то есть что задан некоторый произвольный алгоритм, позволяющий установить, удовлетворяет ли какая-либо последовательность заданным ограничениям, то проблема минимизации оказывается алгоритмически неразрешимой (см. § 9.2). Поэтому нельзя найти метод минимизации, пригодный при любых ограничениях, и можно пытаться лишь искать необходимые и достаточные условия минимизации для заданного частного вида ограничений. Однако, если исключить полный перебор, то даже для наиболее часто встречающихся видов ограничений (например, когда ограничение состоит в том, что на входе могут появляться лишь последовательности заданной длины, либо последовательности любой длины, но не содержащие нескольких одинаковых символов подряд, и др.) такие необходимые и достаточные условия до сих пор не найдены. Некоторые соображения о минимизации в этих случаях приведены в §§ 9.4 и 9.7.

Нам известны лишь две задачи при наличии ограничений на входные последовательности, имеющие полное решение. Это задача о построении минимальной Я-машины в случае, когда она должна работать как конечный автомат, а входные последовательности не содержат нескольких одинаковых символов подряд и задача о построении минимальной П-машины в случае ограничений типа Ауфенкампа (§ ).

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

Мы имеем в виду случай, когда тактность работы проектируемой машины определяется сменой состояний на входе, и поэтому всегда отсутствуют входные последовательности, содержащие подряд несколько одинаковых символов.

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

На первом пути описанный выше второй этап синтеза в той мере, в какой он может быть доведен до конца при указанных ограничениях на входные последовательности, заканчивает формирование таблиц П-машины и далее непосредственно следует третий этап синтеза — переход к абстрактной структуре (см. далее).

На втором же пути необходима дальнейшая обработка таблиц автомата и преобразователя. Она сводится к построению таблиц другой П-машины, работающей в быстрой тактности (которая определяется временем задержки в элементах, используемых для построения П-машины) и воспроизводящей на устойчивых состояниях проектируемую П-машину, работающую в «медленной» тактности, определяемой моментами смены состояний входа.

С этой целью проводится сначала построение какой-либо «быстрой» машины, удовлетворяющей этому условию, а затем минимизация этой полученной машины, т. е. повторяется второй этап синтеза (подробнее см. §§ 10.2 и 10.3). В конечном итоге и на этом втором пути мы получаем таблицы минимальной П-машины и тоже можем перейти к третьему этапу синтеза.

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

В зависимости от количества состояний у элементов, которыми мы располагаем для построения машины, эти функции будут функциями двух-, трех- или вообще -значной логики. Метод кодировки и построения этих функций изложен в § 4.2.

В случае построения автомата на устойчивых состояниях кодировка и построение функций даны в § 5.4.

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

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

Если построение схемы ведется далее на элементах задержки, то число этих элементов предопределено числом уравнений в абстрактной структуре, а оно - заведомо минимально, если доведен до конца второй этап синтеза.

Именно в этом — в получении схемы с наименьшим числом элементов задержки — и состояла цель второго этапа синтеза. Задача технической реализации сводится тогда к построению логических преобразователей, реализующих функции , содержащиеся в правых частях уравнений абстрактной структуры. Из одного и того же набора логических элементов эти преобразователи могут быть построены различными способами. Здесь возникают свои проблемы минимизации, но они касаются уже собственно не последовательностных машин, а преобразователей, т. е. относятся не к динамике, а к статике, и поэтому упоминаются лишь кратко в § 2.6.

Если располагаемый набор логических элементов не содержит готового элемента задержки, то это не исключает возможности построения схем, так как сам элемент задержки, будучи простейшим автоматом, может быть построен из элементов этого набора, например на устойчивых состояниях равновесия.

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

При таком построении схем (на устойчивых состояниях) возникают дополнительные технические затруднения, связанные с тем, что в несинхронизованных системах времена запаздывания элементов не строго одинаковы. Это приводит к угрозе возникновения «состязаний» реле, следствием чего иногда может быть неправильная работа схемы. Опасность состязаний в таких случаях устраняется применением специальных схем — их называют реализациями, — в которых либо в каждом такте срабатывает не более одного реле, либо же в моменты переключений искусственно разрываются цепи обратных связей.

Существуют различные способы построения реализаций, из которых лишь одна кратко описана в § 5.4, так как вопросы реализации не относятся к общей теории конечных автоматов и последовательностных машин. При построении схем на элементах задержки с подведением к ним извне сигнала такта, угрозы возникновений состязаний нет, и поэтому проблема реализации не возникает.

<< Предыдущий параграф Следующий параграф >>
Оглавление