Головна

Перехід від автомата Мура до автомату Мілі і навпаки

  1.  IV. Перехід займенників в інші частини мови
  2.  P-n-перехід
  3.  P-n-перехід в стані термодинамічної рівноваги
  4.  P-n-перехід під впливом зовнішнього напруги
  5.  P_ n перехід в рівноважному стані
  6.  VI. Перехід в прийменники інших частин мови
  7.  VI. Перехід прислівників в інші частини мови

Автомати Мура і Мілі відрізняються функцією виходів.

y (t) = j (q (t)) - для автомата Мура

и

y (t) = j (q (t-1), x (t)) - для автомата Мілі

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

А таблиця переходів автомата Мілі виходить з розширеною таблиці переходів автомата Мура відкиданням першого рядка.

х1


y1 y3 y2
x2
A

A B C
x1 A B A
x1
x1
x3
B
x2

B B C
x3
x3

C A C
x2
y3
y2

x3
x2


y1


 Т. П. A B C
x1 A B A
x2 B B C
x3 C A C
 Т. В. A B C
x1 y1 y3 y1
x2 y3 y3 y2
x3 y2 y1 y2
x1
 Перехід від автомата Мілі до автомата Мура.

qixj ® yij bij
 Т. П.

q1/ b0 q2 q3
x1 q1/ b11 q3/ b21 q2/ b31
x2 q2/ b12 q1/ b22 q3/ b32
 Т. В. q1 q2 q3
x1 y3 y1 y2
x2 y4 y5 y6
    y3 y4 y1 y5 y2 y6
  b0 b11 b12 b21 b22 b31 b32
x1 b11 b11 b21 b31 b11 b21 b31
x2 b12 b12 b22 b32 b12 b22 b32

теорема: (Глушкова)

Таким чином доведена конструктивна теорема, що для довільного автомата Міллі може бути побудований еквівалентний йому автомат Мура має не більше

n * m + 1 станів, де n - число вхідних сигналів, m - число станів вихідного автомата Міллі.




 Аксіоматична теорія обчислення висловлювань |  Несуперечливість і повнота аксіоматичної теорії числення висловів |  Аксіоматичні теорії першого порядку |  система Генцен |  система Аристотеля |  Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |

© um.co.ua - учбові матеріали та реферати