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