Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde sıkça kullanılan sonlu durum makinelerinin (finite state machine, FSM veya Finite State Automaton , FSA) gösteriminde kullanılan iki farklı yöntemdir. Genelde literatürde bir FSM’in gösteriminde en çok moore makinesi kullanılır. Bu iki yöntem (mealy ve moore makinaları) sonuçta bir gösterim farkı olduğu için bütün mealy gösterimlerinin moore ve bütün moore gösterimlerinin mealy gösterimine çevrilmesi mümkündür.
Klasik bir FSM’de bir giriş bir de çıkış bulunur (input / output). Bu değerlerin nereye yazılacağı aslında iki makine arasındaki farkı belirler.
Moore makinelerinde çıkış değerleri düğümlere (node) yazılırken, giriş değerleri kenarlar (edges) üzerinde gösterilir.
Mealy makinelerinde ise giriş ve çıkış değerleri kenarlar (edges) üzerinde aralarına bir taksim işareti (slash) konularak gösterilir. Örneğin 1/0 gösterimi, girişin 1 ve çıktının 0 olduğunu ifade eder.
Basit bir örnek olarak özel veya (exclusive or, Ä) işlemini ele alalım ve her iki makine gösterimi ile de çizmeye çalışalım.
| Girdi 1 | Girdi 2 | Çıktı |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Klasik bir XOR kapısı, yukarıdaki doğruluk çizelgesinde (truth table) gösterildiği üzere iki giriş ve bir çıkıştan oluşur. Bizim makinemiz de ilk girdiden sonra ikinci girdiyi aldığında beklenen çıktıyı vermeli. Ayrıca makine sürekli olarak çalışmaya devam edecek. Örneğin 101011 şeklinde bir veri akışı sağlanması durumunda, sonuç olarak 1Ä0Ä1Ä0Ä1Ä1 değerini hesaplamasını isteriz.
Yukarıdaki gösterim bir mealy makinesidir. Makinede görüldüğü üzere 3 farklı durum arasındaki geçişler üzerine iki adet değer yazılmıştır. Bu değerlerden ilki giriş ikincisi ise çıkış değeridir.
Makineyi beraber okumaya çalışalım.
Makinenin boşluktan bir ok ile başlayan durumu, yani örneğimizdeki S0 durumu, başlangıç durumudur. Bu durumdan başlanarak gelen değerlere göre ilgili duruma geçilir.
Örneğimizi hatırlayalım. Giriş olarak 101011 dizgisini (string) almayı planlamıştık. Bu durumda ilk bitimiz 1 olarak geliyor ve S0 durumunda 1 girişi ile S2 durumuna geçiyoruz. Burada geçiş sırasında kullanılan kenarın üzerindeki değeri okuyalım: 1/0 bunun anlamı 1 geldiğinde geçilecek kenar olması ve çıktının 0 olmasıdır. Yani şu anda çıktımız 0
Ardından gelen değer 0 (yani şimdiye kadar 01 değerleri geldi). En son makinemizdeki durum, S2 durumuydu, şimdi yeni gelen değeri bu durumdaki kollardan takip ediyor ve S1’e giden 0/1 kenarını izliyoruz. Bu kolu izleme sebebimiz, S2 durumundan gidilen tek 0 girdisi kolu olmasıdır. Bu kol üzerindeki ikinci değer olan 1 ise, çıktının 1 olduğudur. Yani buraya kadar olan girdiyi alacak olsaydık 01 için 1 çıktısı alacaktık.
İşlemlere devam edelim ve durumları yazmaya çalışalım:
| Gelen Değer | Durum | Çıkış | Yeni Durum |
| 1 | S0 | 0 | S2 |
| 0 | S2 | 1 | S1 |
| 1 | S1 | 1 | S2 |
| 0 | S2 | 1 | S1 |
| 1 | S1 | 1 | S2 |
| 1 | S2 | 0 | S2 |
Yukarıdaki tablomuzun son halinde, çıkış değeri olarak 0 okunmuştur. Yani örneğimizin neticesi 0 olacaktır.
Aynı örneği moore makinesi olarak tasarlayacak olsaydık:
Moore makinesinde, mealy makinesine benzer şekilde boşluktan gelen bir ok, başlangıç durumunu belirtir.
Makinenin, durumlarında, mealy makinesinde olmayan değerler eklenmiştir. Bu değerler, ilgili durumdaki çıktıyı gösterir. Örneğin makinemiz S1 durumundayken çıktı 0 olarak okunabilir.
Şimdi moore makinesinde, aynı örneği çalıştırıp sonucu karşılaştıralım.
Giriş olarak 101011 dizgisini (string) almayı planlamıştık. Bu durumda ilk bitimiz 1 olarak geliyor ve S0 durumunda 1 girişi ile S2 durumuna geçiyoruz. Bu geçiş sonucunda geldiğimiz S2 durumunda okunan çıktı değeri 0 yani sonuç şimdilik 0.
Ardından gelen 0 değeri ile S3 durumuna geçiyoruz ve çıktımız 1 oluyor. Çünkü S3 durumu 1 çıktısı veren durumdur. Bu şekilde durumları ve durumlar arasındaki geçişleri izlersek, aşağıdaki tabloyu çıkarabiliriz:
| Gelen Değer | Durum | Çıkış | Yeni Durum |
| 1 | S0 | 0 | S2 |
| 0 | S2 | 1 | S3 |
| 1 | S3 | 1 | S4 |
| 0 | S4 | 1 | S3 |
| 1 | S3 | 1 | S4 |
| 1 | S4 | 0 | S2 |
Görüldüğü üzere, makinemiz, örnek girdi için S2 durumunda sonlanıyor ve bu durumda çıktımız 0 olarak okunuyor.
hocam mealy makinedeki tablodan mı çıktı moore makinenin tablosu? onu nasıl oluşturduk? neye göre?
Yazıda belirtmeye çalışmıştım. Amacımız XOR makinesinin çalışmasını gösteren meally ve moore makinesini çizmektir. Yazıda bahsedildiği üzere bir örnek üzerinden çalışma anlatılmıştır.
Örnek : 101011
Bu dizilimde verinin gelmesi halinde çalışan makine örnekleri yukarıda anlatılmıştır. Yani sırasıyla
1 XOR 0 XOR 1 XOR 0 XOR 1 XOR 1
işleminin sonucununu bulan makinenin çalışması ve tabloları yukarıda verilmişitir.
Başarılar
Hocam , çıkışlar neye göre belirleniyor ?
Mealy ve moore makinelerinde giriş ve çıkışlar gösterilmektedir. Örneğin mealy makinesindeki X/Y şeklinde kenarların (edges) üzerinde gösterilen değerlerden ilki (X) giriş ve ikincisi (Y) çıkış değeridir. Benzer şekilde moore makinesinde düğümlerin üzerinde bulunan (nodes) değerler çıkışı ifade eder.
Başarılar
güzel dostum çıkışlar durum tablosuna göre belirlenir. Bilmiyorsan işe hiç başlama bence :d çıkışları bulmak için doğruluk tablosuna bakman lazım. onu da okumayı beceremiyorsan daha bişi sölemiyorum.
paylaşım için teşekkürler. Güzel anlatmışsınız elinize sağlık.
mealy den moore dönşüm veya tam tersinden dönüşüm nasıl yapılıyor?
Dönüşüm için yapılması gereken basitçe tabloları işlemektir. Bunun için çeşitli algoritmalar var (vakit bulursam siteye eklemeye çalışacağım) ancak en basit şekilde şöyle anlatabiliriz sanırım. Örneğin yukarıda önce mealy makinesi verilmiş, bu makinedeki bütün çıktı / düğüm (output / node) ikilileri için moore makinesinde bir düğüm (node) karşılığı olacaktır. Önce bu düğümlerin tespiti ve ardından düğümleri bağlayan kenarların tespiti çevrimi sağlayacaktır.
Başarılar
hocam peki moore makinesinin java dilindeki kodunu yazacak olursak, nasıl bir kod yazmamız gerekir?
bilgisayar mühendisliği okuyan birisi olarak bugüne kadar kafama takılan çoğu konuyu araştırdığımda kendimi en son burada buldum. paylaşımlarınız için teşekkürü bir borç bilirim. emeğinize sağlık, gerçekten çok yardımcı oldu.
Hocam sizi tebrik ediyorum. Şu konuyu anlamak için o kadar site gezdim; bu kadar anlaşılabilir bir başka anlatım bulamadım.
Hocam Moore makinenin çıkış değerlerinde bir hata var gibi (en alt tabloda şekilde değil). Örneğin S2’nin çıkış değeri her zaman 0’dır (1 veya 0 gelse de). Çünkü çıkış değeri kendisinde bulunan değerdir gittiği değil. Aynı durum S4 içinde geçerli. Onun çıkış değerleri de her zaman 1 olacaktır. İyi günler.
İlginiz için öncelikle teşekkür ederim. Öncelikle tablo bir örnek dizgi için hazırlanmış yani şeklin tabloya çevrilmiş hali değil. Girdi (input) olarak 101011 gelmesi durumu için hazırlanmış bir tablo. Sizin bahsettiğiniz durum doğru, yani çıktı her zaman bahsettiğiniz gibi o durumdaki değer oluyor ancak sanırım tabloda net olarak belli olmayan durum çıkışların yeni durum ile ilintili olması durumu. Yani yeni durum olarak gösterilen son kolona bakarsanız buradaki durumlar (states) sizin bahsettiğiniz kurallara uygun. Örneğin S2 ile biten her durumda çıktı 0 ve S4 ile biten her durumda çıktı 1 olmuş. Yine de gözden kaçırdığım bir şey varsa lütfen belirtin yazıda düzelteyim. Teşekkürler
merhabalar, iki uç duruma sahip bir mealy makinesine (C ve D durumu uç durum) denklik bölümlemesi uyguladığımız zaman ilk adım (A,B,E,F,G) (C,D) mi olur yoksa (C) ve (D) diye ayrılır mı?
hocam 0lar 1 den fazla olduğu durumlarda logic1 oluyor. bunun diyagramı nasıl olur
İki şekilde de ilk durumda S0 durumunda 0 ve 1 geçişleriyle S1 ve S2 durumlarına gidilmektedir. Bu durumda 0 XOR 0 ile 0 XOR 1 değerlerinin çıkışı aynı olmaktadır. Çünkü S1 ve S2 durumlarının değeri yani çıkış değeri 0’dır. Bu durumda bir hata var mıdır ?