Синтез цифровых автоматов. Захаров Н.Г - 58 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

57
По правилу 6а получим таблицы переходов (3.14) и выходов (3.15) искомого
синтезируемого автомата Мили.
Таблица 3.14 Таблица 3.15
0 1 2 3 0 1 2 3
0 1 - - - 0 0 0 2 3
1 2 - - - 1 0 1 2 3
2 3 - - - 2 0 2 2 0
3 - - - - 3 0 3 3 0
3.5.3. Синтез автомата Мура
Синтез автомата Мура рассмотрим на следующем примере.
Пример. Построить конечный автомат Мура, возводящий в квадрат двузначные
двоичные числа. Числа подаются на вход автомата последовательно, разряд за разря-
дом (младшими разрядами) и, соответственно, после преобразования выдаются на
выход.
Решение. Поскольку после возведения в квадрат двузначного числа полученное
число может быть четырехзначным, то в первоначально заданной таблице соответст-
вия входные и выходные слова имеют различную длину. Используя прием выравни-
вания длин слов, добавим к входным словам справа по две пустые буквы, так как
числа подаются младшими разрядами. В качестве пустой буквы выберем цифру 0, по-
скольку добавление нуля в старшие разряды входных слов позволяет однозначно вос-
становить их первоначальный вид. После этого добавления получаем автоматное ото-
бражение ϕ, заданное следующей сокращенной таблицей соответствия:
0000 → 0000
1000 → 1000
0100 → 0010
1100 → 1001
Каноническое множество событий для отображения ϕ имеет вид:
S(0) = 0 ∨ 00 ∨ 000 ∨ 0000 ∨ 10 ∨ 100 ∨ 1000 ∨ 01 ∨ 0100 ∨ 11 ∨ 1100,
S(1) = 1 ∨ 010 ∨ 1100.
Первое из найденных событий можно представить более простым регулярным
выражением, записывая вместо первых значений {0}, а вместо трех следующих –
10 {0}. Однако можно поступить проще, применив второй вариант синтеза с исклю-
чением события S(0). Что касается второго события, то для него получим следующее
регулярное выражение:
1 = (1 ∨ 010 ∨ 1100).
Произведем разметку мест в этом выражении, чтобы найти в нем два соответ-
ственных и два подобных места:
1 = | ( | 1 | ∨ | 0 | 1 | 0 | ∨ | 1 | 1 | 0 | 0 | ) | .
0 1 2 3 6 1 4 5 6
0 0 0 1
6

Страницы