Durum Makinesi Diyagramları

Önceki ders bir gevşekliği ölçtü: etkinlik gösterimi 168 tam sıralamayı birden kabul ediyordu ve bu fazlalık bilinçliydi. Kısmi sıra zaten gevşek olmak için yazılır; sayılması gereken şey gevşekliğin büyüklüğüydü.

Durum makinesi gevşek olmak için yazılmaz. Tam tersini iddia eder: bir nesnenin geçebileceği durumları ve o durumlar arasında izin verilen geçişleri sayar, geri kalan her şeyi reddeder. Bir kesinlik iddiasıdır. Bu ders o iddiayı iki yönden sınıyor: makine sistemde gerçekten olan bir diziyi reddediyor mu, ve sistemde hiç olmayan bir diziyi kabul ediyor mu. İki hata ayrı şeylerdir, ayrı sayılırlar, ve birini düzeltmek ötekini büyütür.

İki Yönlü Karşılaştırma

Atölyede bir iş emrinin dört durumu var: açık, ayrıldı, planlı, kapalı. Altı geçiş yazılı. Bu makinenin dili, başlangıç durumundan başlayıp kapalı durumda biten bütün olay dizileridir; en çok altı olaya kadar bakıldığında bu dilde altı dizi var.

Sistemin gerçekten ürettiği dizi sayısı da altı. İki sayı eşit olduğu için makinenin doğru olduğu sanılabilir. Değildir — kümeler eşit değil, yalnız büyüklükleri eşit. Ölçülmesi gereken iki şey var:

• Eksik kabul. Sistemde olan ama makinenin reddettiği dizi. Makine gerçeği dar tutuyor demektir; böyle bir makineye dayanarak yazılan bir denetim, gerçek bir iş emrini hatalı sayar.
• Fazla kabul. Makinenin kabul ettiği ama sistemde hiç olmayan dizi. Makine gerçeği geniş tutuyor demektir; böyle bir makine, olmayacak bir yolu varmış gibi gösterir ve o yol için kod yazılmasına yol açar.

"""Durum makinesi gosterimi: eksik kabul ile fazla kabul ayri ayri sayilir.
Ortak tanimin DURUM_MAKINESI , GERCEK_DIZILER ve makine_dili tanimlari aynen kurulur."""
from itertools import product

DURUM_MAKINESI = {
    "acik":     {"ayir": "ayrildi", "iptal": "kapali"},
    "ayrildi":  {"planla": "planli", "iptal": "kapali"},
    "planli":   {"isle": "planli", "bitir": "kapali"},
    "kapali":   {},
}
BASLANGIC = "acik"
OLAYLAR = ("ayir", "planla", "isle", "bitir", "iptal")

GERCEK_DIZILER = [
    ("ayir", "planla", "isle", "bitir"),
    ("ayir", "planla", "isle", "isle", "bitir"),
    ("ayir", "planla", "isle", "isle", "isle", "bitir"),
    ("ayir", "planla", "isle", "planla", "isle", "bitir"),   # yeniden planlama
    ("ayir", "planla", "iptal"),                             # islemeden once iptal
    ("iptal",),
]


def makine_kabul(makine, dizi, baslangic=BASLANGIC):
    d = baslangic
    for olay in dizi:
        if olay not in makine[d]:
            return False
        d = makine[d][olay]
    return True


def makine_dili(makine, olaylar, uzunluk, baslangic=BASLANGIC):
    kabul = []
    for n in range(1, uzunluk + 1):
        for dizi in product(olaylar, repeat=n):
            d = baslangic
            gecerli = True
            for olay in dizi:
                if olay not in makine[d]:
                    gecerli = False
                    break
                d = makine[d][olay]
            if gecerli and not makine[d]:
                kabul.append(dizi)
    return kabul


# ---- onarilmis makine: iki gecis eklenir
ONARILMIS = {d: dict(g) for d, g in DURUM_MAKINESI.items()}
ONARILMIS["planli"]["planla"] = "planli"
ONARILMIS["planli"]["iptal"] = "kapali"


# ---- DD11: korumali makine. Ayni iki gecis , ustune koruma kosulu.
def son_planladan_sonra_isle(g):
    """planli durumuna en son girildiginden beri en az bir isle oldu mu."""
    yer = max((i for i, e in enumerate(g) if e == "planla"), default=None)
    return yer is not None and "isle" in g[yer + 1:]


KORUMA = {
    ("planli", "planla"): son_planladan_sonra_isle,
    ("planli", "iptal"): lambda g: "isle" not in g,
}


def korumali_kabul(dizi, baslangic=BASLANGIC):
    d, gecmis = baslangic, []
    for olay in dizi:
        if olay not in ONARILMIS[d]:
            return False
        kosul = KORUMA.get((d, olay))
        if kosul and not kosul(tuple(gecmis)):
            return False
        gecmis.append(olay)
        d = ONARILMIS[d][olay]
    return True


def korumali_dil(olaylar, uzunluk, baslangic=BASLANGIC):
    kabul = []
    for n in range(1, uzunluk + 1):
        for dizi in product(olaylar, repeat=n):
            if not korumali_kabul(dizi, baslangic):
                continue
            d = baslangic
            for olay in dizi:
                d = ONARILMIS[d][olay]
            if not ONARILMIS[d]:
                kabul.append(dizi)
    return kabul


# ---- DD12: gecmisi metne degil DURUMA yazmak. planli ikiye bolunur.
BOLUNMUS = {
    "acik":     {"ayir": "ayrildi", "iptal": "kapali"},
    "ayrildi":  {"planla": "planli", "iptal": "kapali"},
    "planli":   {"isle": "islenmis", "iptal": "kapali"},
    "islenmis": {"isle": "islenmis", "planla": "planli", "bitir": "kapali"},
    "kapali":   {},
}


def simge(makine, koruma=0):
    return len(makine) + sum(len(g) for g in makine.values()) + koruma


def olc(ad, dil, kabul_eden):
    fazla = [d for d in dil if d not in GERCEK_DIZILER]
    eksik = [d for d in GERCEK_DIZILER if not kabul_eden(d)]
    return {"ad": ad, "dil": len(dil), "fazla": len(fazla), "eksik": len(eksik),
            "eksik_liste": eksik, "fazla_liste": fazla}


D1 = makine_dili(DURUM_MAKINESI, OLAYLAR, 6)
O1 = olc("dort durum , alti gecis", D1, lambda d: makine_kabul(DURUM_MAKINESI, d))
print("SISTEM  :", len(GERCEK_DIZILER), "gercek gecis dizisi")
print("GOSTERIM:", simge(DURUM_MAKINESI), "simge =", len(DURUM_MAKINESI), "durum +",
      sum(len(g) for g in DURUM_MAKINESI.values()), "gecis")
print("BEDEL   : eksik kabul", O1["eksik"], "| fazla kabul", O1["fazla"])
print()
for d in O1["eksik_liste"]:
    print("  REDDEDILEN:", " ".join(d))
for d in O1["fazla_liste"]:
    print("  FAZLA KABUL:", " ".join(d))
print()
D2 = makine_dili(ONARILMIS, OLAYLAR, 6)
O2 = olc("iki gecis eklenmis", D2, lambda d: makine_kabul(ONARILMIS, d))
D3 = korumali_dil(OLAYLAR, 6)
O3 = olc("iki gecis + iki koruma kosulu", D3, korumali_kabul)
D4 = makine_dili(BOLUNMUS, OLAYLAR, 6)
O4 = olc("bes durum , dokuz gecis", D4, lambda d: makine_kabul(BOLUNMUS, d))
print("makine                          simge  kabul  eksik  fazla")
for o, s in ((O1, simge(DURUM_MAKINESI)), (O2, simge(ONARILMIS)),
             (O3, simge(ONARILMIS, 2)), (O4, simge(BOLUNMUS))):
    print(f"{o['ad']:31s} {s:5d} {o['dil']:6d} {o['eksik']:6d} {o['fazla']:6d}")
print()
print("fazla kabul uzunluk penceresine bagli")
print("pencere  alti gecis  sekiz gecis  koruma kosullu  bolunmus durum")
for u in (4, 5, 6, 7, 8):
    a = len([d for d in makine_dili(DURUM_MAKINESI, OLAYLAR, u)
             if d not in GERCEK_DIZILER])
    b = len([d for d in makine_dili(ONARILMIS, OLAYLAR, u) if d not in GERCEK_DIZILER])
    c = len([d for d in korumali_dil(OLAYLAR, u) if d not in GERCEK_DIZILER])
    e = len([d for d in makine_dili(BOLUNMUS, OLAYLAR, u) if d not in GERCEK_DIZILER])
    print(f"{u:7d} {a:11d} {b:12d} {c:15d} {e:15d}")
print()
print("koruma kosullu makinenin fazla kabulu:", [" ".join(d) for d in O3["fazla_liste"]])
print("bolunmus makinenin fazla kabulu      :", [" ".join(d) for d in O4["fazla_liste"]])

SISTEM  : 6 gercek gecis dizisi
GOSTERIM: 10 simge = 4 durum + 6 gecis
BEDEL   : eksik kabul 2 | fazla kabul 2

  REDDEDILEN: ayir planla isle planla isle bitir
  REDDEDILEN: ayir planla iptal
  FAZLA KABUL: ayir iptal
  FAZLA KABUL: ayir planla bitir

makine                          simge  kabul  eksik  fazla
dort durum , alti gecis            10      6      2      2
iki gecis eklenmis                 12     32      0     26
iki gecis + iki koruma kosulu      14     10      0      4
bes durum , dokuz gecis            14      9      0      3

fazla kabul uzunluk penceresine bagli
pencere  alti gecis  sekiz gecis  koruma kosullu  bolunmus durum
      4           2            5               2               1
      5           2           12               3               2
      6           2           26               4               3
      7           3           58               9               8
      8           4          122              17              16

koruma kosullu makinenin fazla kabulu: ['ayir iptal', 'ayir planla bitir', 'ayir planla isle planla bitir', 'ayir planla isle isle planla bitir']
bolunmus makinenin fazla kabulu      : ['ayir iptal', 'ayir planla isle planla iptal', 'ayir planla isle isle planla iptal']

Üç sayı: sistem 6 gerçek dizi, gösterim 10 simge, bedel 2 eksik kabul ve 2 fazla kabul.

Reddedilen İki Dizi

Makinenin reddettiği iki dizi atölyede gerçekten oluyor. Birincisi yeniden planlamadır: iş işlendikten sonra bir aksaklık çıkıyor, iş yeniden planlanıyor ve yeniden işleniyor. Makinede planlı durumundan planlı durumuna dönen bir geçiş yok, bu yüzden ikinci planla olayı reddediliyor.

İkincisi işleme başlamadan yapılan iptaldir. Makine iptali yalnız açık ve ayrıldı durumlarında kabul ediyor; planlı durumundan iptal yolu yok. Oysa planlanmış ama henüz işlenmemiş bir iş emri iptal edilebiliyor.

İki eksik kabulün ortak yanı, ikisinin de görünmez olmasıdır. Makine yanlış olduğunu söylemiyor; yalnızca o dizileri kabul etmiyor. Diyagrama bakan biri eksikliği fark edemez, çünkü eksik olan şey diyagramda çizili değildir. Ancak gerçek dizilerin listesi elde tutulup makineye tek tek sınatıldığında ortaya çıkar — bu dersin yaptığı da tam olarak budur.

Fazla kabul edilen iki dizi de aynı biçimde çizilidir ama gerçekte yoktur. Stok ayrıldıktan sonra doğrudan iptal etmek ve planlamadan sonra hiç işlemeden bitirmek makinenin izin verdiği yollardır; atölyede ikisi de olmuyor.

Onarmanın Bedeli

Reddedilen iki diziyi kurtarmanın yolu açık: planlı durumuna iki geçiş eklemek. Biri planlı durumundan planlı durumuna planla, öteki planlı durumundan kapalı durumuna iptal. Gösterim 10 simgeden 12’ye çıkıyor. Eksik kabul 0’a iniyor — iki gerçek dizi de artık kabul ediliyor.

Fazla kabul ise 2’den 26‘ya çıkıyor. On üç kat. Makinenin dili altı diziden 32’ye büyüyor ve büyümenin tamamı sistemde karşılığı olmayan dizilerden geliyor.

Nedeni yapısaldır. Planlı durumuna kendine dönen bir planla geçişi eklemek, “işlendikten sonra yeniden planlanabilir” demez; “planlı durumundayken her an, kaç kez olursa olsun yeniden planlanabilir” der. Durum makinesi geçmişi tutmaz; tuttuğu tek şey içinde bulunduğu durumdur. Bir geçiş eklendiğinde o geçiş, durumun ulaşılabildiği bütün yollardan sonra açık hâle gelir. Amaçlanan tek bir yol için eklenir, elde edilen bütün yollar için açılır.

Buradan çıkan kural şudur: eksik kabulü kapatmanın bedeli fazla kabuldür. İki hata birbirinin tersi yönde durur ve bir gösterim ikisini birden sıfıra indiremez — indirebilseydi gösterim sistemin kendisi olurdu, izdüşümü değil. Bir durum makinesi değerlendirilirken bu yüzden tek bir sayı yetmez; iki sayı yan yana yazılır.

Koruma Koşulu Bedeli Kısar

Gösterimin bu duruma karşı bir aracı var: koruma koşulu. Bir geçişe, ancak sağlandığında alınabileceği bir koşul yazılır. İki yeni geçişe iki koruma koşulu ekleyelim (DD11): yeniden planlama ancak planlı durumuna girildiğinden beri en az bir işleme olduysa, iptal ancak hiç işleme yapılmadıysa alınabilsin.

Sonuç tabloda: 14 simge, eksik kabul yine 0, fazla kabul 26’dan 4’e iniyor. İki simge karşılığında yirmi iki yanlış dizi kapandı.

Kalan dördün ikisi zaten baştan vardı — stok ayrılınca doğrudan iptal ve planlamadan sonra hiç işlemeden bitirme. Yani iki geçiş ve iki koruma koşulunun getirdiği net fazla kabul 2’dir, ve bu ikisi de yeniden planladıktan sonra hiç işlemeden bitirme durumudur. Koruma koşulu bedeli sıfırlamıyor, kısıyor.

Kısmanın kendi bedeli de var. Koruma koşulu bir metindir; durum çizgesinin yapısında değil, geçişin üzerinde bir cümle olarak durur. Makinenin yapısı onu sınamaz — sınayan şey, koşulu okuyup gerçekleştiren koddur. Gösterim iki simge daha yazdı ama sınanabilirliği çizgeden metne taşıdı, ve metin olarak yazılan bir kısıt yanlış olabilir. Nitekim burada da öyle: yazılan koşul yeniden planlamadan sonra doğrudan bitirmeyi engellemiyor.

Geçmişi Metne Değil Duruma Yazmak

Koruma koşulunun yaptığı iş aslında geçmişi hatırlamaktır: “planlı durumuna girdiğimden beri işleme oldu mu” sorusu, durumun taşımadığı bir bilgiyi soruyor. Bu bilgiyi taşımanın ikinci bir yolu var — onu bir duruma çevirmek.

Planlı durumu ikiye bölünüyor (DD12): planlanmış ama henüz işlenmemiş iş için planlı, işleme başlanmış iş için işlenmiş. İptal yalnız planlı durumundan, bitirme yalnız işlenmiş durumundan alınabiliyor; yeniden planlama işlenmiş durumundan planlı durumuna dönüyor. Sonuç beş durum ve dokuz geçiş, yani 14 simge — koruma koşullu makineyle tam olarak aynı sayı.

Ölçüm iki yerde ondan iyi çıkıyor. Eksik kabul yine 0, fazla kabul 4 yerine 3. Üstelik kalan üçün biri zaten baştan vardı ve koruma koşullu makinenin kapatamadığı iki dizi — yeniden planlayıp hiç işlemeden bitirmek — burada yapısal olarak kapalı: planlı durumunda bitir geçişi yoktur. Buna karşılık bölünmüş makine yeniden planladıktan sonra iptali kabul ediyor ve bu iki dizi atölyede olmuyor.

Asıl fark sayıda değil, kısıtın nerede durduğundadır. Bölünmüş makinede kural çizgenin kendisindedir: bir geçişin olup olmadığı bakılarak görülür. Koruma koşullu makinede kural bir cümledir ve cümlenin doğru okunup doğru gerçekleştirildiği çizgeye bakarak anlaşılamaz. Aynı 14 simge, iki farklı yerde duruyor; biri gösterimin sınanabilir kısmında, öteki sınanamaz kısmında.

Sayı Pencereye Bağlıdır

Orta alttaki tablo bir uyarı taşıyor. Bir makinenin dili çoğunlukla sonsuzdur — planlı durumundaki isle döngüsü her uzunlukta dizi üretir. Bu yüzden “fazla kabul 26” mutlak bir sayı değil, en çok altı olaylık diziler penceresinde sayılmış bir değerdir.

Pencere büyüdükçe dört makinenin dördü de büyüyor, ama farklı hızlarda. Altı geçişli taban makine 4’ten 8’e giden pencerede 2, 2, 2, 3, 4 veriyor; sekiz geçişli makine 5, 12, 26, 58, 122; koruma koşullu makine 2, 3, 4, 9, 17; bölünmüş durumlu makine 1, 2, 3, 8, 16. Taban makine dar kaldığı için yavaş büyüyor, onarılmış makine her uzunlukta yeni yollar açtığı için hızlı.

Bunun karşılaştırma için anlamı şudur: iki makinenin fazla kabulü ancak aynı pencerede karşılaştırılabilir, ve pencere yazılmadan verilen bir fazla kabul sayısı okunamaz. Kapsam oranının paydası neyse, fazla kabulün penceresi odur.

Özet

• Durum makinesi iki yönde birden yanılabilir: eksik kabul sistemde olanı reddetmek, fazla kabul sistemde olmayanı kabul etmektir. İki sayı ayrı ayrı yazılır; dil ile gerçek dizi sayısının eşit olması makinenin doğru olduğunu göstermez.
• Dört durumlu, altı geçişli makine 10 simge ile atölyenin 6 gerçek dizisinden 2’sini reddediyor (yeniden planlama ve işlemeden önce iptal) ve sistemde olmayan 2 diziyi kabul ediyor.
• İki geçiş eklemek eksik kabulü 0‘a indiriyor ama fazla kabulü 2’den 26’ya çıkarıyor: on üç kat. Durum makinesi geçmişi tutmadığı için eklenen geçiş, durumun ulaşıldığı bütün yollardan sonra açılır.
• Eksik kabulü kapatmanın bedeli fazla kabuldür. Bir gösterim iki hatayı birden sıfırlayamaz; sıfırlayabilseydi izdüşüm değil sistemin kendisi olurdu.
• İki koruma koşulu 14 simgeyle fazla kabulü 26’dan 4’e indiriyor; planlı durumunu ikiye bölmek aynı 14 simgeyle 3’e indiriyor. Fark sayıda değil, kısıtın çizgede mi metinde mi durduğundadır.
• Fazla kabul sayısı uzunluk penceresine bağlıdır: pencere 4’ten 8’e çıkınca taban makine 2’den 4’e, onarılmış makine 5’ten 122‘ye, koruma koşullu makine 2’den 17’ye, bölünmüş makine 1’den 16’ya gidiyor. Pencere yazılmadan verilen fazla kabul sayısı okunamaz.

Sonraki Adım

Bu konu davranışın dört gösterimini saydı. Kullanım senaryosu iç adımları bilerek attı ve 128 sistemi ayırt edemedi; sıra gösterimi 24 izin birini gösterdi; etkinlik gösterimi 168 tam sıralamayı birden kabul etti; durum makinesi iki yönde birden yanıldı. Dördünün ortak yanı, her birinin sistemin zaman içindeki yanını göstermeye çalışmasıdır.

Sonraki konu zamanı hiç konuşmuyor. Bir sistemin neyi sakladığını soruyor: hangi varlıklar var, hangi öznitelikleri taşıyorlar, aralarında hangi ilişkiler kurulu. Kavramsal model bakım atölyesi için 26 olgu söylüyor: 5 varlık, 12 öznitelik, 4 ilişki, 5 kısıt. Bu 26 olgunun bir şemaya inerken nasıl davrandığı, davranış gösterimlerinden farklı bir kayıp türü ortaya çıkarır — model yalnız unutmuyor, aynı zamanda uyduruyor, ve ikisi ayrı ayrı sayılıyor.