учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С., страница 4

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

Должен обеспечиваться детерминированный и достаточно простой переход вт описания абстрак ного конечнвго автомата в некоторой допустимой исходной форме к опксанию в заданной форме без какай бы то ни было потери информации. 4. Наглядность представления. Используемые формы и средства представлении конечного автомата должны позволять с достаточной наглядностью интерпретировать все освовиыв свойства абстрактного конечного автомата, вошедшие в вге определение, и хотя бы некоторые друГие, которые могут представлять интерес.

6. Удобство в использовании. Применяемые формы и средства представления абстрактного конечного автомата должны допускать выполнение тех преобразований, катерые могут бытъ необходимы на тех илн иных этапах анализа и синтеза абстрактных и реальных автоматов. Желательно, чтобы каждая из кспользуемых форм была особенно удобна дпя кахогото определенного преобразования.

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

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

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

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

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

и ), и число столбцов, равное числу символов в алфавите внутренних состояний (1.е. 1 ). Таким образом, задаютси все возможные пары текущих (т.е.' в момент времени г ) зна- 17 чепий аргументов характеристических функций. В плетках самих таблиц проставляются текущие выходиые сигвалы (дли таблицы выходов) ипи впутрекпие состояния, которые ластупят х следующему тахту времапи (т.е для момеита времеви 1+1). Влутрепкие состояипя залепляют клетки таблицы переходов (можие быдо бы сказать — ввутреплкх переходов). Рассмотрим цример таких табляп для вехоторого автомата Мили, кмеющего следующ,ле алфавиты: Х=~х„х~,хз~, у = ~ф~, $ ) и У=(б„у„,у,).

Тогда таблицы выходов (табл 1) и переходов (табл. 2) могут иметь, лапркмер, следующий вид: Таблица 1 Таблица 2 Часто для компактности записи таблицы выходов и переходов совмещают. Тогда каждую клетку совмещепвей таблицы делят диагональю иа две части: в Таблица. 3 верхней обычно записывают буду- щее ввутрвивее состоявие, в вкж- 5„ вей - текупаий выходной сигвал. Х Нкже приводится совмешепвая таб- 5, 5, 5 пвца (табл.

3) для автомата, ра- нее представленного табл, 1 и 2, , „ Когда число пар х,. 5( сравпк5з тельно невелико, таблипу выходов 5д 5, з к переходов строят клогда иным У, У, У, способом, несколько папомивающим 5 5 построепие истивпостляй табпицьь 7~ р р р Это построепка лепясрапственпя м г Ф связывает в одной строке пары преобразования (1 ° 11).

Такая таблица для уже рассматриваемого автомата приводится пкже (табл 4). Для автомата Мура таблицы выходев и переходов отдель по ие составляются в силу простоты функция выходов, Совме- 18 щелкая: таблица строится несхольхо иным способом пе сравиеилю с таблицей длк автомата Мили Числе- стрех талой таблицы равно ж +1: добавпяетсп отдельлая строка длк выхядкых слгвалев, зависящих только от виутрелвкх состоявкй. Эта строка ебычля расцопагается в низу таблицы. В клетках остальных строк проставляются будущие ввутревике состяяиля. Пример тахой таблицы приводится для пехетярого автомата Мура, обладающего следующими алфавитами; Х ( Х„ хг' хФ 1', ~(~~' М 5 -( 5,, ~, У~, 5,~ ( аб .

6). Длк автомата Мура может быть составлепа табикца, акалагичпая табл. 4. Ее построение ечевкцпе и поэтому межет быть рпущеие. Таблица 6 Таблица 4 Таблица 6 Все приведенные таблицы соответствовали полностью опрепелевиым автоматам Мили и Мура. При описавии частичного автомата длп пе определепиых пар й, у( должпы оставаться свободными клетки в таблицах типа табл. 1,2,3 и 6 кли строки в таблипах ткпа табл. 4. Часто в указаивых местах ста- 19 х/ к а1/ ж я.

яьб д У, вятся прочерки. В качестве примера частичного автомата возьмем автомат Мини, кмеюший те же алфавиты, Что и рассмотренный ранее, с тем, однако, отпнчием, что дпя парйЯ и ш,к преобразование (1.11) не будет опредепено. Тогда совмещенная таблнпа переходов и выходов для этогэ автомата будет иметь вид табп. 6. Рассмотренное табличное представление абстрактно о конечного автомата достаточно удобно при решении целого ряда задач. анапиза и синтеза автоматов.

Его основными дэстзинствами являютсн предельная . простота сеставпеиия и непосредственное отображение преобразования (1 ° 11). 2,3. П едставпенне абстрактного конечного автомата Формой представпеннн абстрактного автомата, позвопиющей весьма наглндно интерпретировать рнд его свойств, явпяетсн его представление в виде направпенного графа. Построенке этого графа осушествпяется сходным образом дпи 1 автоматов Минн и Мура во бь всех их компонентах, кроме Й;/ к х отображении выходных сигнапов (это естественно, посконьху функции выходов дпя 5 автоматов Мили н Мура рае- к а) й пнчны). Дпн обоих типов автом»- тов их внутренние состояния н представляются вершинами графа (рис.

6). Внутренние Рнс, 6. Представление на переходы от одного состояния графе входных и выходных переменных, внутренних со- к другому изображаются стояний н перэходор дли правленными дугами. И дпн автоматов Мали ~61 и авто- автомата Минн и дпя автоматов Мура (б) Ю мата Мура входной сигнап, вызывающий этот переход из предыдущего состояния 8 ( а) в поспедуюшее Я ( а +1), приписывается соответствующей дуге так, как это показано на рис.

6. Ддя автомата Мили выходной сигнал У (6), определяемый парой я; Лй, ставится в соответствие самой дуге (см.рис, 6,а). Дпя автомата Мура выходной сигнал зависит только от внутреннего состояния и поэтому приписывается соответствующей вершине' (см.рнс. 6,6).Таким образом, на графах отображаютси обе характеристические й нкпии абстрактного конечного автомата. Иногда прн составленкн графа автомата дпя упрошення самого вида графа несколько дуг, обозначающих одинаковые внутренние переходы, во при разпичных входных снгвапах, ебъединяются в одну дугу, около которой записывается поги ~еская сумма усповий перехода (рнс 6) ° Иа рнс.

7 н 6 изображены графы автоматов, ранее заданных в табпичной форме в п 2,2* х,~ Рнс. 6. Объединение дуг,обла- Рнс. 7. Граф автомата, задан- дающих общими исходными и ного табп. 3 конечными внутренними со- стояниями Рнс. 8. Граф автомата, задан- Рнс. 9. Граф автомата Мура с ного табл. 6 вершннамн различных типов Представление автомата в виде графа дает значительные удобства при решении ряда задач. В частности, с помощью графа очень легко осуществить споварное преобразование.

Пусть, например, на автомат Мили (см.рис. 7) с заданным 21 начальным внутренним состоянием к, будет подано входное слово Х ( х,, Х„х~, я~, Х,~ . Тогда последовательный проход по графу, начиная от его вершины У, с выбором дуг, соответствующих симвопам входного снова, сразу же даст выходное слово У - ~д, и,, у, у, у,~ н скоко внутренних состояний 5. ~у,,у~,г,р,, 8~, я ) . Естественно, тот же результат можно было бы подучить и с помощью табличного задания автомата (см.табп. 3), однако его понученне на основе графа значительно нагляднее и легче контролируется, что позвопяет резко сократить опасность ошибки.