Пред. страница   . След. страница   Раздел   Содержание

_____________________________________________________________________________________________________________

4.5. Построение А - преобразователей

Задача построения или синтеза автомата обычно формулируется следующим образом. Дано словесное описание работы некоторого устройства, требуется найти таблицу или диаграмму переходов, описывающую работу этого устройства.

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

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

4.5.1. Построение А – преобразователя по заданной Т - грамматике

Каждый детерминированный автомат реализует некоторый перевод, который можно восстановить, построив транслирующую грамматику по диаграмме переходов автомата. Для практических применений представляет интерес обратная задача – построение автомата по заданному переводу. В общем случае можно считать, что заданный перевод представлен в виде транслирующей грамматики, поскольку в разделе 4.2 было показано, как можно по заданной СУ – схеме построить Т – грамматику, задающую такой же перевод, как СУ – схема. Однако детерминированный автомат можно построить не для любой Т – грамматики. Для того чтобы грамматика допускала построение детерминированного преобразователя, она должна удовлетворять определенным условиям, которые определяются следующим утверждением.

Утверждение. Для каждой Т – грамматики, у которой входная грамматика Г_вх и выходная грамматика являются автоматными, причем входная грамматика не содержит правил с одинаковыми левыми частями, в правой части которых стоят одинаковые терминалы, можно построить детерминированный автомат.

Действительно, если заданная Т грамматика содержит правила вида

А ® а {х} В и А ® а {х} С

или

А ® а {х} В и А ® а {у} C

или

А ® а {х} В и А ® а {у} B,

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

В качестве примера рассмотрим построение автомата для грамматики, которая задает перевод слов, состоящих из символов {a,b} таким образом, что если слово начинается символом a , то все последующие символы b символами у. Если же слово начинается символом b, то все последующие символы a символами x. Последним символов каждого входного слова является знак минус, а выходного – знак плюс. Правила этой грамматики имеют вид:

I ® а {a} A и I ® b {b} B

А ®а {a} A и А ®b {y} A

B ®а {х} В и B ® b{b} B

А ®- {+} Z и B ® - {+} Z

Диаграмма переходов автомата, реализующего перевод, заданный этой грамматикой, приведена на рисунке 4.8.

Рис. 4.8. Диаграмма переходов автомата, построенного по приведенной выше грамматике

В заключение следует отметить, что автомат, построенный описанным способом по Т - грамматике, выполняет преобразование входного слова длиной n за n тактов работы.

4.4.2. Построение А - преобразователя по заданному конечному переводу.

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

Определение. Множество, состоящее из конечного числа пар, образованных из слов входного и выходного алфавитов, называется конечным переводом.

Для того чтобы построить устройство, выполняющее заданный перевод, он должен обладать следующими свойствами:

a) Перевод должен быть детерминированным, то есть все входные слова перевода должны быть различными,

b) Перевод должен содержать слова одинаковой длины.

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

Допустим, что заданный детерминированный конечный перевод, состоящий из m пар слов:

t= {(a₁,b₁),(a₂,b₂),…,(a_m,b_m)},

где a_i – слова входного алфавита P , а b_i – слова выходного алфавита W.

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

Для переводов такого типа справедливо следующее утверждение.

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

Обозначим начальный и конечный символы искомой грамматики как I и Z. Для каждой пары слов a=x₁,x₂,…,x_n и b=y₁,y₂,…,y_n. Заданного перевода t выберем n-1 нетерминальный символ и построим правила грамматики следующим образом:

I ®x₁ y₁ U₁, I₁®x₂ y₂ U₂, …, U_n-1® x_n y_n Z.

Выполним аналогичное построение для каждой пары заданного перевода, получим искомую транслирующую грамматику. Если построенная грамматика содержит правила первого вида:

X ®a {w} U и X ®a {w} V,

то автомат, построенный по такой грамматике, будет детерминированным. Если же грамматика содержит правила второго или третьего вида:

X ®a {w₁} U и X ®a {w₂} V или X ®a {w₁} U и X ®a {w₂} U,

то построение автомата, выполняющего заданный перевод за n тактов, является невозможным.

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

X ®a {w} U₂ и X ®a {w}U₂,…, X ®a {w} U_k

Удаляются все правила кроме первого. Нетерминальные символы U₂,U₂,…,U_k, входящие в левые части других правил грамматики заменяются символом U₂ и удаляются из вспомогательного словаря грамматики. В результате такого преобразования правил грамматики могут образоваться группы правил первого вида и правил второго вида. Появление правил второго вида говорит о том, что построение автомата для заданного перевода невозможно. Появившиеся группы правил первого вида можно повторно преобразовать описанным выше способом.

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

В качестве примера применения рассмотренного способа построим автомат для перевода

t_4.1= {(100,abc), (101,aba)}.

Транслирующая грамматика, построенная для этого перевода, имеет вид:

I ®1 a A₂, A₂®0 b A₂, A₂® 0 c z,

I ®1 a B₂, B₂®0 b B₂, B₂® 1 a z,

Эта грамматика содержит два правила первого вида с нетерминальным символом I в левой части правил. Исключим одно из правил и заменим символ B₂ символом A₂, получим правила грамматики вида:

I ®1 a A₂, A₂®0 b A₂, A₂® 0 c z,

A₂®0 b B₂, B₂® 1 a z.

Полученная грамматика опять содержит два правила первого вида с символом A₂ в левой части правил. Исключим одно из правил и заменим символ В₂ символом А₂, получим правила грамматики

I ®1 a A₂, A₂®0 b A₂ A₂® 0 c z, А₂® 1 a z,

которой соответствует детерминированный автомат. Диаграмма переходов этого автомата приведена на рисунке 4.9.

Рис. 4.9. Диаграмма переходов автомата, реализующего перевод t_4.1.

В качестве второго примера рассмотрим построение автомата для следующего перевода:

t_4.2= {(011,ааа), (010,abb)}.

Транслирующая грамматика, построенная для этого перевода, имеет вид:

I ®0 a A₂, A₂®0 а A₂, A₂® 1 а Z,

I ®0 a B₂, B₂®1 b B₂, B₂® 0 b Z.

После исключения правил первого типа грамматику можно записать так:

I ®0 a A₂, A₂®1 b A₂, A₂® 1 а Z, A₂®1 b B₂, B₂® 0 b Z.

Эта грамматика содержит правила второго вида с символом А₂ в левой части правил. Следовательно, построение автомата для заданного перевода невозможно.

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

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

Утверждение. Для каждого детерминированного конечного перевода, состоящего из слов одинаковой длины, можно построить автомат, выполняющий преобразование слов заданного перевода не более, чем за 2n –1 тактов.

Идея построения такого автомата основана на том, что все входные слова детерминированного перевода различны, а, следовательно, для определения слова, подаваемого на вход, можно использовать детерминированный распознаватель. Такой распознаватель обрабатывает входное слово n тактов. На последнем такте работы распознавание входного слова заканчивается, и этот такт можно использовать для формирования первого символа выходного слова. Для формирования остальных символов выходного слова потребуется еще n–1 такт работы автомата.

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

Процедура построения автомата, реализующего заданный перевод, заключается в следующем. Во-первых, добавим пустой символ e во входной и выходной алфавиты заданного перевода. Во-вторых, преобразуем каждую пару слов перевода, дописывая n–1 пустой символ справа к входному слову, и n-1 пустой символ слева к выходному слову. В результате такого преобразования пары перевода должны иметь вид:

(a_i ee…e, ee…e b_i ).

n-1 раз n-1 раз

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

В качестве примера рассмотрим построение автомата для следующего перевода:

t_4.3= {(00,bb), (01,ab)}.

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

t`_4.3= {(00e, ebb), (01e,eab)}.

Правила транслирующей грамматики, задающей этот перевод, имеют вид:

I ®0 e A₂, A₂®0 b A₂, A₂® e b z.,

I ®0 e B₂, B₂®1 а B₂, B₂® e b z..

После преобразования правил первого вида получим:

I ®0 e A₂, A₂®0 b A₂, A₂®1 а В₂, A₂® e b z., B₂® e b z.

Диаграмма переходов автомата, построенная по этой грамматике, показана на рисунке 4.10.

Рис.4.10. Диаграмма переходов автомата, реализующего перевод t_4.3.

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

4.4.3. Примеры построения автоматов

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

Построение начинается с рассмотрения начального состояния I. Для этого состояния следует определить, какие входные символы могут быть поданы на вход автомата, и для каждого символа построить дугу диаграммы переходов, отмеченную входным и соответствующим ему выходным символами, а также новое состояние. Затем для каждого нового состояния следует определить допустимые входные символы и построить для них дуги и состояния диаграммы переходов. Если входные последовательности содержат повторяющиеся фрагменты символов, то состояние, соответствующему последнему символу фрагмента, следует соединить дугой с состоянием, которое соответствует началу фрагмента.

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

Чтобы показать возможности этого способа, рассмотрим несколько примеров.

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

Построение начнем с начального состояния I. Входная последовательность может начинаться символом ноль или последовательностью нулей любой длины, которым должны соответствовать выходные символы 0. Учитывая, что входные символы 0 не должны изменять состояние и выход автомата, построим дугу в виде петли состояния I и отметим эту дугу символами 0,0. Построенный переход соответствует правилу грамматики I®0 {0} I. Для первого символа 1, содержащегося во входной последовательности построим дугу, исходящую из состояния I, и новое состояние A. Построенную дугу отметим символами 1,0. После символа 1 во входной последовательности может следовать любое число нулей, которым соответствует нулевой выходной символ. Следовательно, построим еще одну дугу в виде петли состояния A и отметим эту дугу символами 0,0. Для второго символа 1, содержащегося во входной последовательности, построим дугу, исходящую из состояния A, и новое состояние B. Рассуждая аналогичным образом, можно построить правила грамматики для исходных последовательностей, содержащих три и четыре единицы. Для этого нужно дополнить диаграмму четырьмя переходами и состояниями C и D.

Согласно заданию, каждому пятому символу единицы во входной последовательности должен соответствовать символ единицы в выходной последовательности. Кроме того, следует учесть, что после поступления пятой единицы счет должен начинаться заново, поэтому проведем на диаграмме дугу, соединяющую состояния D и I, которую отметим символами 1,1.

В результате получаем диаграмму переходов счетчика, изображенную на рисунке 4.11.

Рис. 4.11. Диаграмма переходов счетчика

Этой диаграмме соответствует Т-грамматика, схема которой имеет вид:

R = { I®0{0}I, I®1{0}A, A®0{0}A, A®1{0}B,

B®0{0}B, B®1{0}C, C®0{0}C, C®1{0}D

D®0{0}D, D®1{1}I }.

В качестве второго примера рассмотрим построение автомата, преобразующего последовательность нулей на входе в последовательность символов a, а группы единиц во входной последовательности, состоящие из одной, двух и трех символов, соответственно в последовательности b, bc, bcd. Из задания следует, что входной алфавит автомата должен состоять из двух символов {0,1} , а выходной – из четырех символов {a, b, c, d} . Построение диаграммы переходов искомого автомата начнем с начального состояния I.

Для входных последовательностей, начинающихся нулем или состоящих из нулей, построим петлю у состояния I, которую отметим символами 0,a. Для последовательностей, содержащих единицы, введем состояние A и соединим это состояние дугой с I, которую отметим символами 1,b. Чтобы учесть входные последовательности, содержащие группы нулей, следующих за единицей, построим дугу, соединяющую состояния A и I, и отметим ее символами 0,a. Для последовательностей, содержащих две единицы, введем новое состояние B, которое соединим дугой с состоянием A, а дугу пометим символами 1,c. Поскольку продолжением входной последовательности может быть 1 либо один или несколько нулей, то добавим новое состояние C, соединив его дугой, отмеченной символами 1,d, с состоянием B. Кроме того, соединим состояние B с состоянием I дугой, отмеченной символами 0,a.

Учитывая, что переход из состояния С может происходить под действием входных символов 0 и 1, а также то обстоятельство, что для группы единиц во входных последовательностях могут повторяться, получаем диаграмму переходов искомого автомата в виде, изображенном на рисунке 4.12.

Рис. 4.12. Диаграмма переходов автомата, преобразующего группы единиц в символы {a, b, c, d}.

Построенный автомат реализует перевод, который определяется схемой следующей грамматики:

R = { I®0aI, I®1bA, A®0aI, A®1cB,B®0aI, B®1dC, C®0aI, C®1bA }.

И еще один пример. Пусть требуется построить автомат, выполняющий сложение двух двоичных чисел, подаваемых на вход последовательно, начиная с младших разрядов. Если предполагается складывать n – разрядные числа, то на вход автомата должны подаваться n+1 разрядные числа, старшие разряды которых равны нулю.

Входной алфавит автомата состоит из четырех символов P = {00,01,10,11}, каждый из которых образован двумя цифрами складываемых чисел. Выходной алфавит состоит из двух символов W = {0,1}, которые определяют цифры суммы.

Построение диаграммы переходов начнем с начального состояния I. Входные последовательности могут начинаться любым символом входного алфавита, поэтому нужно построить четыре дуги, исходящих из состояния I. Выходные символы, соответствующие цифрам суммы, для входных символов 00, 01, 10 определяются правилами сложения и не влияют на формирование цифр старших разрядов. Следовательно, дуги соответствующие этим символам должны подставлять собой петли состояния I и быть отмеченными входными и выходными символами: 00,0, 01,1, и 10,1.

Если же входной символ равен 11, то цифра суммы – ноль, но возникает перенос, который влияет на формирование последующих выходных символов. Чтобы учесть это влияние, создадим новое состояние A. Если при сложении предыдущих разрядов был перенос, и оба следующих разряда равны нулю, то сумма равна единице. Этому случаю должен соответствовать переход из состояния A в состояние I, отмеченный символами 00,1. Если же был перенос, и один из следующих разрядов складываемых чисел равен единице, то сумма равна нулю, кроме того, возникает перенос в следующий разряд. Эта ситуация должна отражаться петлями состояния A, отмеченными символами: 01,0 и 10,0. Наконец, если был перенос, и обе цифры складываемых чисел равны единице, то цифра суммы также равна единице, кроме того, выполняется перенос в старший разряд. Этому случаю должна соответствовать петля состояния A, отмеченная символами 11,1.

Итак, получаем диаграмму переходов автомата, показанную на рисунке 4.13.

Рис. 4.13. Диаграмма переходов автомата для сложения двоичных чисел.

Построенный автомат выполняет перевод, описываемый грамматикой, схема которой имеет вид:

R = { I®00 {0} I, I®01 {1} I, I®10 {1} I, I®11 {0} A,

A®00 {1} I, A®01 {0} A, A®10 {0} A, A®11 {1} A}.

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

____________________________________________________________________________________________________________

Пред. страница   . След. страница   Раздел   Содержание