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
| Wejście | 1 | 0 | 1 | 1 | |
| Państwo | q0 | q2 | pytanie 1 | q2 | q2 |
| Wyjście | 0 | 0 | 1 | 0 | 0 |
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:
