Практична частина

1.Представити число у двійковому коді: прямому, зворотному, доповнюючому та у коді Грея.

Приклад Перетворити число 35₁₀ у двійковий прямий, зворотній, доповнюючий та код Грея.

Розв’язання. Спочатку представимо десяткове число у вигляді прямого двійкового коду:

35	:	2	=	17	+	залишок 1 = а0
17	:	2	=	8	+	залишок 1 = а1
8	:	2	=	4	+	залишок 0 = а2
4	:	2	=	2	+	залишок 0 = а3
2	:	2	=	1	+	залишок 0 = а4
1	:	2	=	0	+	залишок 1 = а5

Тепер записуємо отримані розряди у зворотньому порядку.

Тобто, 35₁₀ = A₂ = a₅ a₄ a₃ a₂ a₁ a₀ = 100011₂ .

Зворотній код B₂ = b₅ b₄ b₃ b₂ b₁ b₀ отримується шляхом інверсії кожного розряду прямого коду: B₂ = 100011₂=011100₂ .

Доповнюючий код D₂  знаходиться шляхом додавання одиниці до числа, представленого у зворотньому коді B₂:

D₂ = B₂  + 1 = 011100₂ + 1₂ = 011101₂ .

Кожний біт коду Грея встановлюється в нуль або одиницю залежно від значень відповідного та наступного бітів A₂:

g₀ = 0, тому що значення бітів a₀ = 1 та a₁ = 1 однакові;

g₁ = 1, тому що значення бітів a₁ = 1 та a₂ = 0 неоднакові;

g₂ = 0, тому що значення бітів a₂ = 0 та a₃ = 0 однакові;

g₃ = 0, тому що значення бітів a₃ = 0 та a₄ = 0 однакові;

g₄ = 1, тому що значення бітів a₄ = 0 та a₅ = 1 неоднакові;

g₅ = 1 тому що значення біту a₅ = 1 а значення відсутнього наступного біту a₆ завжди приймається рівним нулю, тобто їхні значення неоднакові.

В результаті отримана відповідь: g₅ g₄ g₃ g₂ g₁ g₀ = 110010₂ .

2.Перетворити абстрактний автомат Мілі, заданий графом у еквівалентний автомат Мура. Результат представити у вигляді графа та таблиці переходів. Пояснити виконані перетворення.

Пояснення

Кожен стан q_i початкового автомата Мілі породжує стільки станів автомата Мура, скільки різних вихідних сигналів виробляється в початковому автоматі при попаданні в стан q_i.

Кожному стану початкового автомата Мілі ставиться у відповідність множина пар виду (qi,yj), де yj, вихідний сигнал, що виробляється автоматом при переході в qi. Кожній такій парі в автоматі Мура відповідатиме окремий стан, тобто стан qi розщеплюється на стільки станів, скільки різних вихідних символів виробляється при переході в qi.

Розглянемо перехід від автомата Мілі до автомата Мура на прикладі автомата:

Мілі: Мура:

Як випливає зі схеми автомата Мілі при переході автомата у стан q₁ виробляються вихідні сигнали y₁ або у₂, при переході до q₂ – y₂ або у₃, q₃ – y₁ або у₃, q₀ – y₃. Кожній парі станів q_i - вихідний сигнал yj, який генерується при переході у цей стан, поставимо у відповідність стан q_ik еквівалентного автомата Мура з тим же вихідним сигналом y_j : q₁₁ = (q₁, y₁), q₁₂ = (q₁, y₂), q₂₁ = (q₂, y₂), q₂₂ = (q₂, y₃), q₃₂ = (q₃, y₁), q₃₁ = (q₃, y₃), q₀ = (q₀, y₃), тобто кожен стан q_i автомата Мілі породжує деяку множину Q_i станів еквівалентного автомата Мура: Q₁ = { q₁₁, q_­12}, Q₂ = { q₂₁, q₂₂ }, Q₃ = { q_31, q₃₂ }, Q₀ = { q₀ }. Як видно, в еквівалентному автоматі Мура кількість станів 7. Для побудови графа автомата Мура поступаємо таким чином. Оскільки у автоматі Мілі є перехід зі стану q₀ у стан q₁ під дією сигналу x₁ з видачею y₁, то із множини станів Q₁ = { q₁₁, q_­12}, породжуваних станом q₁ автомата Мілі в автоматі Мура має бути перехід в стан (q₁, y₁) = q₁₁ під дією сигналу x₁ і т.д. Граф еквівалентного автомата Мура представлений на другому рисунку (зправа).