Moore ve Mealy Makineleri
Sonlu otomata, her geçişe karşılık gelen çıktılara sahip olabilir. Çıktı üreten iki tür sonlu durum makinesi vardır -
- Mealy Makinesi
- Moore makinesi
Mealy Makinesi
Bir Mealy Makinesi, çıkışı mevcut giriş kadar mevcut duruma bağlı olan bir FSM'dir.
6 tuple (Q, ∑, O, δ, X, q 0 ) ile tanımlanabilir burada -
Q sonlu bir durum kümesidir.
∑ giriş alfabesi adı verilen sonlu bir semboller kümesidir.
O çıktı alfabesi adı verilen sonlu bir semboller kümesidir.
δ : Q × ∑ → Q olduğu giriş geçiş fonksiyonudur
X çıktı geçiş fonksiyonudur burada X: Q × ∑ → O
q0herhangi bir girişin işlendiği ilk durumdur (q 0 ∈ Q).
Bir Mealy Makinesinin durum tablosu aşağıda gösterilmiştir -
| Mevcut durum | Sonraki durum | |||
|---|---|---|---|---|
| input = 0 | input = 1 | |||
| Durum | Çıktı | Durum | Çıktı | |
| → a | b | x 1 | c | x 1 |
| b | b | x 2 | d | x 3 |
| c | d | x 3 | c | x 1 |
| d | d | x 3 | d | x 2 |
Yukarıdaki Mealy Makinesi'nin durum diyagramı -
Moore Makinesi
Moore makinesi, çıktıları yalnızca mevcut duruma bağlı olan bir FSM'dir.
Bir Moore makinesi 6 tuple (Q, ∑, O, δ, X, q 0 ) ile tanımlanabilir burada -
Q sonlu bir durum kümesidir.
∑ giriş alfabesi adı verilen sonlu bir semboller kümesidir.
O çıktı alfabesi adı verilen sonlu bir semboller kümesidir.
δ : Q × ∑ → Q olduğu giriş geçiş fonksiyonudur
X çıkış geçiş fonksiyonudur, burada X: Q → O
q0herhangi bir girişin işlendiği ilk durumdur (q 0 ∈ Q).
Moore Makinesinin durum tablosu aşağıda gösterilmiştir -
| Mevcut durum | Sonraki Eyalet | Çıktı | |
|---|---|---|---|
| Giriş = 0 | Giriş = 1 | ||
| → a | b | c | x 2 |
| b | b | d | x 1 |
| c | c | d | x 2 |
| d | d | d | x 3 |
Yukarıdaki Moore Makinesinin durum diyagramı şöyledir:
Mealy Makinesi ve Moore Makinesi
Aşağıdaki tablo bir Mealy Makinesi'ni Moore Makinesi'nden ayıran noktaları vurgulamaktadır.
| Mealy Makinesi | Moore Makinesi |
|---|---|
| Çıktı hem mevcut duruma hem de mevcut girdiye bağlıdır | Çıktı yalnızca mevcut duruma bağlıdır. |
| Genellikle, Moore Machine'den daha az duruma sahiptir. | Genellikle, Mealy Machine'den daha fazla duruma sahiptir. |
| Çıkış fonksiyonunun değeri, mevcut durumdaki giriş mantığı yapıldığında geçişlerin ve değişikliklerin bir fonksiyonudur. | Çıkış işlevinin değeri, durum değişikliği meydana geldiğinde mevcut durumun ve saat kenarlarındaki değişikliklerin bir işlevidir. |
| Mealy makineleri girdilere daha hızlı tepki verir. Genellikle aynı saat döngüsünde tepki verirler. | Moore makinelerinde, çıktıların kodunu çözmek için daha fazla mantık gerekir ve bu da daha fazla devre gecikmesine neden olur. Genellikle bir saat döngüsünden sonra tepki verirler. |
Moore Machine'den Mealy Machine'e
Algoritma 4
Input - Moore Makinesi
Output - Mealy Makinesi
Step 1 - Boş bir Mealy Machine geçiş tablosu formatı alın.
Step 2 - Tüm Moore Machine geçiş durumlarını bu tablo formatına kopyalayın.
Step 3- Moore Machine durum tablosunda mevcut durumları ve bunlara karşılık gelen çıktıları kontrol edin; bir durum Q i çıkışı m ise, Q i'nin sonraki durumda göründüğü her yerde bunu Mealy Makinesi durum tablosunun çıkış sütunlarına kopyalayın .
Misal
Aşağıdaki Moore makinesini ele alalım -
| Mevcut durum | Sonraki Eyalet | Çıktı | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b | 1 |
| b | a | d | 0 |
| c | c | c | 0 |
| d | b | a | 1 |
Şimdi onu Mealy Machine'e dönüştürmek için Algoritma 4'ü uyguluyoruz.
Step 1 & 2 -
| Mevcut durum | Sonraki Eyalet | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Durum | Çıktı | Durum | Çıktı | |
| → a | d | b | ||
| b | a | d | ||
| c | c | c | ||
| d | b | a | ||
Step 3 -
| Mevcut durum | Sonraki Eyalet | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Durum | Çıktı | Durum | Çıktı | |
| => a | d | 1 | b | 0 |
| b | a | 1 | d | 1 |
| c | c | 0 | c | 0 |
| d | b | 0 | a | 1 |
Mealy Makinesi Moore Machine
Algoritma 5
Input - Mealy Makinesi
Output - Moore Makinesi
Step 1- Mealy makinesinin durum tablosunda bulunan her durum (Q i ) için farklı çıktıların sayısını hesaplayın .
Step 2- Qi tüm çıkışlar aynıysa, durumda, Q kopya i . N'nin ayrı çıkış varsa, q kırmak i Q n durumları içine içinden = 0, 1, 2 .......
Step 3 - Başlangıç durumunun çıkışı 1 ise, başlangıca 0 çıkış veren yeni bir başlangıç durumu ekleyin.
Misal
Aşağıdaki Mealy Makinesi'ni ele alalım -
| Mevcut durum | Sonraki Eyalet | |||
|---|---|---|---|---|
| a = 0 | a = 1 | |||
| Sonraki Eyalet | Çıktı | Sonraki Eyalet | Çıktı | |
| → a | d | 0 | b | 1 |
| b | a | 1 | d | 0 |
| c | c | 1 | c | 0 |
| d | b | 0 | a | 1 |
Burada, 'a' ve 'd' durumları sırasıyla yalnızca 1 ve 0 çıkış verir, bu nedenle 'a' ve 'd' durumlarını koruyoruz. Ancak 'b' ve 'c' durumları farklı çıktılar üretir (1 ve 0). Öyleyse bölüyoruzb içine b0, b1 ve c içine c0, c1.
| Mevcut durum | Sonraki Eyalet | Çıktı | |
|---|---|---|---|
| a = 0 | a = 1 | ||
| → a | d | b 1 | 1 |
| b 0 | a | d | 0 |
| b 1 | a | d | 1 |
| c 0 | c 1 | C 0 | 0 |
| c 1 | c 1 | C 0 | 1 |
| d | b 0 | a | 0 |