К эквивалентному автомату Мили

Кафедра автоматизированных систем обработки

Информации и управления

 

 

ТЕОРИЯ АВТОМАТОВ

 

Методические указания по курсу

''Основы дискретной математики''

для студентов специальности 0646

 

 

Пермь 1998

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

Универсальность и сравнительная простота автоматов обусловили широкое использование автоматных моделей на практике. Теория автоматов, например, успешно используется при построении узлов цифровых вычислительных машин; при построении программ и, в частности, лексических анализаторов в трансляторах.

Абстрактная теория автоматов выделяет два основных способа использования автоматов: преобразование входной последовательности символов в выходную (синтез дискретных устройств) и проверка правильности входной последовательности символов (синтез программных анализаторов).

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

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

 

 

ПОНЯТИЕ АВТОМАТА

 

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

Автомат есть система

 

U=<X,Y,Q,f (q, x), j (q, x) >,

 

где X={x₁, x₂, …, x_n} – входной алфавит;

Y={y₁, y₂, …, y_m} - выходной алфавит;

Q={q₀ ,q₁, …, q_s} - алфавит внутренних состояний;

f (q, x): Q*X®Q – функция переходов;

j (q, x):Q*X®Y – функция выходов.

Часто фиксируют также начальное состояние автомата q₀ÎQ. Такие автоматы называют инициальными (будем рассматривать только инициальные автоматы).

Законы функционирования автоматов:

а) для автоматов первого рода (автоматов Мили)

q (t) = f (q (t-1), x (t)),

y (t) = j (q (t-1), x (t));

б) для автоматов второго рода

q (t) = f (q (t-1), x (t)),

y (t) = j (q (t), x (t));

в) для правильных автоматов второго рода (автоматов Мура)

q (t) = f (q (t-1), x (t)),

y (t) = j (q (t)).

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

Входной алфавит в описании задан явно: X={1,2,3}.

Выходной алфавит будет содержать буквы (сигналы): Б- выдает билет, В- возвращает деньги, Н- ничего не выдает, т.е. Y{Н,Б,В}.

Внутренние состояние будем отождествлять с суммой, которую помнит автомат. Будем иметь в виду, что после продажи билета или возврата денег автомат помнит нулевую сумму: Q={q₀, q₁, q₂}, здесь индекс соответствует сумме.

Автомат в виде графа представлен на рис. 1

Рисунок 1

 

Это автомат Мили. Надпись 1/Б; 2,3/В у стрелки q₂q₀ означает, что если в состоянии q₂ будет принят сигнал 1, выходной сигнал будет Б, а для входных сигналов 2 и 3 выходным будет В. Этот же автомат можно представить в виде двух таблиц: таблицы переходов (табл.1) и таблицы выходов (табл.2)

 

Таблица 1 Таблица 2

	q0 q1 q2   q1 q2 q0   q2 q0 q0   q0 q0 q0		q0 q1 q2   Н Н Б   Н Б В   Б В В

 

 

 

 

2. Построить автомат, на вход которого могут поступать монеты 1, 2 и 3 коп. Автомат выдает сигнал “чет.” (Ч), если сумма опущенных монет четная, и “нечет.” (Н), если нечетная (рис.2).

Рисунок 2.

 

Сумма 0 считается четной. Это автомат Мура, т.е. его выходной сигнал однозначно определяется состоянием, в которое автомат перешел, поэтому выходные сигналы приписаны прямо к состояниям. Этот же автомат можно представить отмеченной таблицей переходов (табл.3).

 

Таблица 3

	Н	Ч
	qн	qч
	qч	qн
	qн	qч
	qч	qн

 

Автомат называется частичным, если некоторые комбинации “состояние– входной сигнал” не могут возникнуть в реальных условиях. При этом в графе автомата появляются состояния, из которых определены выходы не для всех входных сигнаов (т.е. присутствуют не все стрелки), а в таблицах переходов и выходов (и в отмеченной таблице переходов) имеются незаполненные клеточки.

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

 

ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ АВТОМАТОВ

 

Два атомата называются эквивалентными, если они имеют одинаковые входные и выходные алфавиты и на одинаковые входные слова выдают одинаковые выходные слова.

 

 

Переход от автомата Мили

К эквивалентному автомату Мура

 

Законы функционирования автоматов Мили и Мура отличаются функцией выходов. Поскольку каждой паре ”состояние – входной сигнал” автомата Мили может соответствовать свой выходной сигнал, а в автомате Мура выходной сигнал приписываенся состоянию, то каждой паре q_i x _j автомата Мили ставится в соответствие состояние синтезируемого автомата Мура b _{i j .}

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

Пример. Возьмем ранее рассмотренный автомат Мили (см. табл. 1 и 2). Перерисуем табл. 1, указав в клеточках i j состояния b_ij синтезируемого автомата Мура (табл. 4). Попав в любое из таких состояний, автомат Мура должен обеспечить дальнейшую реализацию прежней функции переходовтолько уже в ”терминах” состояний автомата Мура, т.е. состояния b_0, b_03, b_12, b_13, b_21, b_22, и b₂₃ должны обеспечить переходы, аналогичные тем, которые имели место для состояния q₀ в автомате Мили, b₀₁ -аналогичное q₁, а b₀₂ и b₁₁ -аналогичные q₂. Полученный автомат Мура приведен в табл. 5.

Пусть не смущает, что автомат получился явно избыточным, уменьшить число состояний- дело техники. Главное, что он ”работает” точно так же, как и исходный автомат Мили.

q0 b0 q1 q2   q1 b01 q2 b11 q0 b21   q2 b02 q2 b12 q0 b22   q3 b03 q0 b13 q0 b23

Таблица 4

 

Таблица 5

	Н Н Б Н Б В Б В В   b0 b01 b02 b03 b11 b12 b13 b21 b22 b23   b01 b11 b21 b01 b21 b01 b01 b01 b01 b01   b02 b12 b22 b02 b22 b02 b02 b02 b02 b02   b03 b13 b23 b03 b23 b03 b03 b03 b03 b03

Таким образом, существует стандартный прием, с помощью котороко можно преобразовать автомат Мили в эквивалентных ему автомат Мура. Причем, если в автомате Мили n внутренних состояний и m входных то в полученном автомате Мура будет n* m+1 состояний.

 

 

Переход от автомата Мура

К эквивалентному автомату Мили

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

Рис. 3

 

Не менее просто осуществляется переход для автомата, заданного в табличной форме. Это можно увидеть, если для рис. 3 нарисовать соответствующие таблицы переходов и выходов (табл. 6 и 7).

 

Таблица 6 Таблица 7

	qн qч   qч qн   qн qч   qч qн		qн qч   ч н   н ч   ч н

 

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

 

МИНИМИЗАЦИЯ АВТОМАТОВ

 

 

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

Два состояния автомата называются 1-эквивалентными, если, находясь в любом из этих состояний, автомат на один и тот же входной сигнал (входное слово длиной в 1) выдает один и тот же выходной сигнал. Два состояния автомата называются К- эквивалентными, если, начиная с любого из этих состояний, автомат на любые одинаковые слова длины К выдает одинаковые выходные слова (также длины К). Если два состояния К- эквивалентны для любых К, то их называют (просто) эквивалентными. Множество попарно эквивалентных состояний образует класс эквивалентности.

Смысл минимизации состоит в выявлении классов эквивалентности и замене каждого класса одним состоянием.

Процедура минимизации состоит в следующем:

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

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

3. Процедура разбиения на классы эквивалентности продолжается до те пор, пока при очередном шаге К- эквивалентные классы не совпадут с (К-1)-эквивалентными, т.е. получатся эквивалентные классы.

4. Все состояния, входящие в один класс эквивалентности, заменяются одним состоянием.

Пример. Рассмотрим автомат Мили заданный табл. 8 и 9.

 

Таблица 8 Таблица 9

 

 

1 – эквивелентные классы определяются из табл. 8, 2 – эквивалентные из табл. 9, а 3 – эквивалентные и просто эквивалентные из табл. 10.

 

Таблица 10 Таблица 11 Таблица 12

		α β γ x1 y1 y1 y2 x2 y2 y2 y2

 

В качестве имен состояний минимального автомата возьмем имена классов. Минимальный автомат представлен табл. 11 и 12.

 

РАСПОЗНАЮЩИЕ АВТОМАТЫ

 

Распознающий автомат – это автомат Мура, в котором фиксируется начальное состояние и подмножество состояний FÍQ, называемое множеством заключительных состояний. Говорят, что автомат допускает (принимает, распознает, представляет) данное слово, если реакцией на это слово может быть переход автомата в одно из заключительных состояний.

Примеры. 1. Автомат (рис. 4) с начальным состоянием 1 и заключительным F₁ и F₂ допускает слова, в которых имеются только парные вхождения букв a и b, например, a a, a a a a a a, b b a a и т.д.

Рис. 4

2.Для распознавания часто используются частичные автоматы (рис.5), допускающие тоже множество слов, что и автомат, показанный на рис.4.

 

 

Рис. 5 Рис. 6

 

Здесь начальное состояние 1, а заключительное F. Слово считается недопустимым, если в результате реакции на него автомат не остановится в заключительном состоянии или если будет подан запрещенный (для данного состояния) входной сигнал. Например, воздействие входного слова ab на автомат вызовет переход в состояние 2 по букве a, но в этом состоянии не определен переход по букве b, следовательно, слово ab недопустимо. Если считать пустое (не содержащее ни одной буквы) слово допустимым, то можно еще более упростить частичный автомат, объединив начальное и заключительное состояния (рис.6).

 

3.Одним из наиболее широко используемых на практике типов распознающих автоматов является частичный недетерминированный автомат. Недетерминизм проявляется в том, что из одного состояния по одному и тому же входному сигналу возможны переходы в различные состояния, т.е. функция переходов заменяется отношением переходов. Недетерминированный автомат (рис.7) принимает, например, слова ab, aa, bb, bba и т.д. здесь начальное состояние A, а заключительное - F.

Рис. 7

 

Таблица переходов данного автомата будет иметь вид табл.13.

Таблица 13

 

	A	B	C	F
a	B,C		F
b	B	C,F

 

 

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

 

A ® aB A:: = aB / bB / aC

A ® bb B:: = bC / b

A ® aC C:: = a

B ® bC

B ® b

C ® a

 

Такого рода грамматики называют регулярными, или автоматными.

Автоматы такого типа будут рассмотрены в связи с изучением теории формальных языков и грамматик.

 

УПРАЖНЕНИЯ

 

Звездочками отмечены задания, для которых приводятся решения.

1.Построить (синтезировать) автомат по содержательному описанию.

1.1.* На вход автомата могут поступать сигналы R, S и T. На входной сигнал R автомат выдает выходной сигнал 0, на S- выходной сигнал 1 и на T- выходной сигнал, противоположный предыдущему выходному сигналу. Для определенности считаем, что в начальном состоянии автомат помнит ’’предыдущий’’ выходной сигнал 0.

1.2.* Автомат имеет две входные шины X₁ и X_2, на которые в дискретные моменты независимо друг от друга могут поступать сигналы 0 или 1. В автомате вычисляется функция f=x₁ Å x₂, а затем определяется, сколько раз с учетом данного момента времени функция f принимала значение 1. Выходной сигнал Y может иметь три значения:

Y = 0, если f = 0;

Y = 1,если f = 1 и суммарное число случаев, включая данный, когда f

равнялась единице, нечетно;

Y = 2 в остальных случаях.

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

На вход автомата могут поступать символы, допустимые в языке ПЛ/1. Автомат выдает сигнал U, если на вход поступил идентификатор, в противном случае выдает сигнал Н. Считаем, что идентификатор впереди и сзади ограничен пробелами.

Автомат Мура, принимая на входе монеты 10; 15 и 20 коп., выдает сигнал П, если значение текущей суммы опущенных монет кратно 50 и не кратно 1 руб.; выдает сигнал Р, если сумма кратна 1 руб.; во всех остальных случаях выдает сигнал 0.

1.20* На вход автомата по двум шинам x₁ и x₂ поступают различные комбинации из нулей и единиц, воспринимаемые как двоичные числа. Автомат выдаёт сигнал Н, если сумма поступившых чисел нечётная, К - если сумма чисел кратная четырём, и 4 – если сумма чисел чётная, но не кратна четырём.

 

2. * Привести примеры автоматов:

2.1 имеющих два внутренних состояния;

2.2 имеющих одно внутренних состояние;

2.3 не имеющих ни одного внутреннего состояния.

 

3. Придумать автомат, имеющий не менее трёх и не более пяти состояний.

 

4. Преобразовать автомат Мили в автомат Мура:

 

4.1 Таблица 14 Таблица 15

	q0 q1 q2 x1 q1 q0 q2 x2 q2 q1 q1		q0 q1 q2 x1 y2 y1 y3 x2 y4 y5 y6

 

5. Преобразовать автомат Мура в автомат Мили:

 

5.1 * Таблица 24

	y1 y2 y3   q1 q2 q3 x1 q2 q3 q3 x2 q1 q2 q3

 

7. Минимизировать автомат Мили:

 

7.1 * Таблица 30 Таблица 31

	x1               x2		x1 y1 y3 y3 y1 y1 y1 y1 x2 y2 y2 y2 y2 y2 y2 y2

 

 

α                   β                   γ

7.2 * Таблица 32 Таблица 33

α                   β                   γ

 

8. Минимизировать автомат Мура.

 

8.1* Таблица 44 8.2* Таблица 45

 

		y1 y1 y2 y2 y1 y1 y2   a b c d e f g x1 d g g d d c g x2 a b b b b a b x3 e b b g g d d
	y1 y2 y1 y1 y1 y1 y2                 x1               x2

 

9. Синтезировать распознающий автомат, описываемы регулярной (автономной) грамматикой.

9.1.*На вход могут поступать символы, допустимые в языке ПЛ/1. Автомат распознаёт идентификаторы (без ограничения по длинне).

9.2.*Автомат распознаёт десятичные константы с фиксированной точкой, допустимые в ПЛ/1.

9.5.*Автомат распознаёт условный оператор ПЛ/1, которыё имеет вид:

IF е THEN t₁ [ELSE t₂]

Считаем, что на этом этапе анализа ключевые слова языка, а также выражения е и группы операторов t₁ и t₂ заменены отдельными символами. Квадратные скобки говорят о том, что соответствующий фрагмент может отсутствовать.

11.. Для недетерминированного автомата, заданного грамматическими правилами, построить эквивалентный детерминированный автомат.

11.1.* А::= ab / aC 11.2. A::= ab / bB / aC

B::= b B::= bc / b

C::= a C::= a

 

12. Придумать свои упражнения, аналогичные приведённым, и выполнить их.

 

 

РЕШЕНИЯ.

 

1.1. Соответствующий автомат Мура представлен на рис. 8.

 

Рис. 8

 

1.2. Каждой комбинации значений х ₁ и х ₂ припишем букву (рис. 9). Автомат Мили представлен на рис. 10.

	x1 x2 A     D     C     D

Рис. 9 Рис. 10

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

 

 

Рис. 2

 

Так, например, состояние 2 говорит о том, что светофор открыт для вертикальной дороги, а на горизонтальной ожидает одна машина. Жирные черточки, соответствующие положения светофора, возьмем в качестве символов сигналов (│, ─). Автомат представлен табл.14.

 

 

	▬ ▬ ▬ ▬ ▬ ▬               В             Г

 

Таблица 14.

 

1.4. Примем обозначения: б – буква, ц – цифра, ð - пробел, π – любой другой входной символ, ~ - выходной сигнал «неопределённо». Автомат Мура может иметь вид рис. 12 (длину идентификатора не ограничиваем).

 

 

 

 

 

рис. 12 рис 13.

 

П р и м е ч а н и е. Для данного содержательного описания частичный недетерминированный распознающий автомат может иметь вид рис. 13, где 1 – начальное состояние, а F –заключительное. Соответствующая автоматная грамматика может быть записана как:

1::= б / б2

2::= б2 / ц2 / б / ц

 

1.6. Этот «безобидный» с виду автомат требует, судя по всему, 21 состояния. Не полностью (для наглядности) заполненная табл.15 иллюстрирует возможное решение. Начальное состояние 0 используется только на первом шаге. Следует обратить внимание на появление состояния 5.

 

 

Таблица 15

 

О

О

О

О

О

О

О

О

О

О

П

О

О

О

О

О

О

О

О

О

Р

х10

х15

х25

 

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

 

1.20. Решение может иметь вид рис. 14.

 

Рис. 14

 

1.2.. Наиболее ходовые примеры – это одноразрядные двоичные элементы памяти (хранящие один бит информации): триггер, ферритовое кольцо, реле и т.п.

 

2.2.. Фактически, это автоматы без памяти, может служить любая комбинационная схема.

 

2.3.. Автомат без состояния не имеет смысла.

 

▬ y2 y4 y1 y5 y3 y6   b0 b01 b02 b11 b12 b21 b22 x1 b01 b11 b21 b01 b11 b21 b11 x2 b02 b12 b22 b02 b12 b32 b22

4.1.. Результирующий автомат Мура будет иметь вид табл. 16.

 

 

Таблица 16

 

5.1.. Результирующий автомат Мили будет иметь вид табл. 17, 18.

	q1 q2 q3 x1 q2 q3 q3 x2 q1 q2 q3		q1 q2 q3 x1 y3 y2 y2 x2 y1 y3 y2

 

Таблица 17 Таблица 18

 

7.1. Определим 1-эквивалентные классы, используя таблицу выходов, и с помощью таблицы переходов определим 2-эквивалентные классы (табл.19). Определение 3-эквивалентных классов показано в табл.20.

 

a b c

a b c

Таблица 19 Таблица 20

 

 

 

a b c d

Определим далее 4-эквивалентные классы (табл. 21). 3-эквивалентные классы совпали с 4-эквивалентными, следовательно, мы получили классы эквивалентных состояний. Минимальный автомат будет иметь вид табл. 22 и 23.

 

х1	b	c	c	d	d	d	d
х2	b	c	c	c	c	c	a

a b c d

Таблица 21

a b c d х1 y1 y3 y1 y1 х2 y2 y2 y2 y2

a b c d х1 b c d d х2 b c c a

 

 

Таблица 22 Таблица 23

 

 

7.2. Минимальный автомат будет иметь вид табл.24, 25.

	a b c d e α c d a a b β c c c e e γ b a c d b		a b c d e α           β           γ

 

Таблица 24 Таблица 25

 

Отметим, что при различном кодирование классов эквивалентности можно получить не абсолютно одинаковые, а изоморфные (т.е. одинаковые с точностью до имен состояний) автоматы.

8.1. 1-эквивалентные классы определяются по первой строке отмеченной таблицы переходов, 2-эквивалентные – на основе содержания этой таблицы (табл.26).

 

 

	y1	y1	y1	y1	y1	y1	y1
x1	a	a	a	a	a	a	a
x2	a	a	a	a	b	a	a

a b a c

 

Таблица 26

 

В результате выполнения всех возможных разбиений (табл.27, 28, 29) получим минимальный автомат Мура (табл.30).

 

 

Таблица 27 Таблица 28

 

		y1 y1 y1 y1 y2   a b c d e x1 a b a a a x2 d a a e a

 

 

Таблица 29 Таблица 30

 

Обратим внимание на то важное обстоятельство, что используемая процедура минимизации в ряде случаев может быть ”излишне” универсальной. Она не учитывает того, что мы рассматриваем лишь инициальные автоматы. (Начальное состояние во всех примерах, независимо от использования различных систем обозначения, в таблицах всегда идет первым). А например, для инициального автомата с начальным состоянием а (см. табл. 30) невозможен переход в состояние с, т.е. состояние с является недостижимым. Следовательно, его можно исключить. Из исходного автомата можно убрать недостижимые состояния до начала процесса минимизации. (Существуют и другие ”аномальные” ситуации. Какие, на ваш взгляд?).

 

8.2. Минимальный автомат представлен табл. 31.

 

	y1	y1	y2	y2	y1	y1
	α	β	γ	ε	η	δ
x1	ε	ε	ε	ε	ε	γ
x2	α	β	β	β	β	α
x3	η	β	β	ε	ε	ε

 

Таблица 31

 

9.1. См. рис.13 и соответствующее примечание.

9.2. В ПЛ/1 константы с фиксированной точкой могут иметь один из следующих видов:

а) S a₁ … a_n · b₁ … b_n

б) S a₁ … a_n

в) S a₁ … a_n

г) S· b₁ … b_m

где S – либо пусто, либо + или -; a_i (i = 1,n) – цифры целой части, b_j (j = 1,m) – цифры дробной части.

Распознающий автомат можно представить в виде рис.15, где А- начальное, а F – заключительное состояние.

 

 

 

Рис.15

 

Однако этот распознающий автомат не дает регулярной грамматики (из заключительного состояния есть выходящая стрелка). Для получения регулярной грамматики введем дополнительное состояние (рис.16).

 

Рис.16

Соответствующая грамматика будет:

А:: = u C |+ B |– B |+ D |– D |· D |u E |u

B:: = u C |·D

D:: = u E | u

E:: = u E | u

 

9.5. См. рис.17. Считаем, что t₁ и t₂ заканчивается символом:.

 

Рис.17

 

 

10.1. См. рис.18.

 

 

Рис.18

 

11.1. A:: = a D

D:: = a / b

 

СПИСОК ЛИТЕРАТУРЫ

1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962.

2. Гилл А. Введение в теорию конечных автоматов. – М.: Наука, 1966.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергия, 1960.

4. Вавилов Е.Н., Портной Г.П. Синтез схем электронных цифровых машин. – М.: Советское радио, 1963.

5. Бузунов Ю.А., Вавилов Е.Н. Принципы построения цифровых вычислительных машин. Киев: Техника, 1972.