Maszyna Moore'a jest maszyną o skończonych stanach, w której o następnym stanie decyduje bieżący stan i bieżący symbol wejściowy. Symbol wyjściowy w danym momencie zależy wyłącznie od aktualnego stanu maszyny. Maszynę Moore’a można opisać za pomocą 6 krotek (Q, q0, ∑, O, δ, λ), gdzie:

 Q: finite set of states q0: initial state of machine ∑: finite set of input symbols O: output alphabet δ: transition function where Q × ∑ → Q λ: output function where Q → O 

Przykład 1:

Diagram stanu maszyny Moore'a to

Tabela przejściowa dla Moore Machine to:

Java rzuca znak na ciąg

W powyższej maszynie Moore'a wyjście jest reprezentowane przez każdy stan wejściowy oddzielony znakiem /. Długość wyjściowa maszyny Moore'a jest większa niż wejściowa o 1.

Wejście: 010

Przemiana: δ (q0,0) => δ(q1,1) => δ(q1,0) => q2

Wyjście: 1110(1 dla q0, 1 dla q1, ponownie 1 dla q1, 0 dla q2)

Przykład 2:

Zaprojektuj maszynę Moore'a generującą uzupełnienie do 1 danej liczby binarnej.

Rozwiązanie: Aby wygenerować uzupełnienie 1 danej liczby binarnej, prosta logika jest taka, że ​​jeśli na wejściu jest 0, to na wyjściu będzie 1, a jeśli na wejściu będzie 1, to na wyjściu będzie 0. Oznacza to, że są trzy stany. Jeden stan to stan początkowy. Drugi stan polega na przyjmowaniu zer jako danych wejściowych i tworzeniu wyniku jako 1. Trzeci stan polega na przyjmowaniu jedynek jako danych wejściowych i wytwarzaniu wyników jako 0.

Stąd maszyna Moore'a będzie:

Weźmy na przykład jedną liczbę binarną 1011

W ten sposób otrzymujemy 00100 jako uzupełnienie 1011, możemy zaniedbać początkowe 0, a otrzymanym wynikiem jest 0100, które jest uzupełnieniem 1011. Tabela transakcji wygląda następująco:

Zatem maszyna Moore'a M = (Q, q0, ∑, O, δ, λ); gdzie Q = {q0, q1, q2}, ∑ = {0, 1}, O = {0, 1}. tabela przejść pokazuje funkcje δ i λ.

postać normalna Greibacha

Przykład 3:

Zaprojektuj maszynę Moore'a dla binarnej sekwencji wejściowej takiej, że jeśli ma podciąg 101, wyjście maszyny A, jeśli na wejściu ma podciąg 110, wygeneruje B, w przeciwnym razie wygeneruje C.

Rozwiązanie: Aby zaprojektować taką maszynę, sprawdzimy dwa warunki, a są to 101 i 110. Jeśli otrzymamy 101, na wyjściu będzie A, a jeśli rozpoznamy 110, na wyjściu będzie B. W przypadku innych ciągów, na wyjściu będzie C.

Częściowy diagram będzie wyglądał następująco:

Teraz wstawimy możliwości zer i jedynek dla każdego stanu. W ten sposób maszyna Moore'a staje się:

wyrażenie regresji w Javie

Przykład 4:

Skonstruuj maszynę Moore'a, która sprawdza, czy ciąg wejściowy zawiera parzystą czy nieparzystą liczbę jedynek. Maszyna powinna dać na wyjściu 1, jeśli w ciągu znaków znajduje się parzysta liczba jedynek, i 0 w przeciwnym razie.

Rozwiązanie:

Maszyna Moore'a będzie:

To jest wymagana maszyna Moore'a. W tej maszynie stan q1 akceptuje nieparzystą liczbę jedynek, a stan q0 akceptuje parzystą liczbę jedynek. Nie ma ograniczeń co do liczby zer. Zatem dla wejścia 0 pętlę własną można zastosować w obu stanach.

Przykład 5:

Zaprojektuj maszynę Moore'a z alfabetem wejściowym {0, 1} i alfabetem wyjściowym {Y, N}, która generuje Y jako wynik, jeśli sekwencja wejściowa zawiera 1010 jako podciąg, w przeciwnym razie generuje N jako wynik.

Rozwiązanie:

Maszyna Moore'a będzie: