Sonlu Otomatlar

İleri Algoritmalar kursu iki soruyu bilerek açıkta bıraktı. Gezgin satıcı ve Hamilton yolları derslerinde “bu problem neden zor” sorusu ayrı birer bölümde bu kursa havale edildi; kursun kapanışı ise şunu sordu: bazı problemler için kaba kuvvetten daha iyisinin bilinmemesi, bilgimiz hakkında mı yoksa problemler hakkında mı bir gerçektir. İki borç da aynı yere bakar. Birincisi tek bir problemin zorluğunu sorar, ikincisi zorluğun nerede durduğunu. O kursun son ölçümü bir aday yolu sınamanın 11, böyle bir yolun olmadığını göstermenin ortalama 11.601 adım harcadığını gösteriyordu ve orada açıkça yazıldığı gibi bu bir gözlemdi, bir kanıt değil. Gözlemi adlandırmak ve nerede kanıta dönüştüğünü söylemek bu kursun işidir.

Bu kurs bir hız kursu değildir. Sorduğu şey bir yordamın kaç adım harcadığı değil, bir modelin neyi hiç yapamadığıdır. Ama bir kuramın sonuçları koşturularak kanıtlanamaz. Bu yüzden burada ölçülen şey kuramın kendisi değil, sonlu bir bütçenin ne söyleyip ne söyleyemediğidir. Her derste üç sayı yan yana durur: bütçe, bütçenin yanıtladığı ve bütçenin yanıtlayamadığı. Kursun kuralı da buradan gelir: bir sonucun sayısı bütçesiyle birlikte yazılır, ve bütçesi yazılmayan “çözülemez” iddiası ölçülmemiş sayılır. Sonlu bir koşum hiçbir yerde “bu dil tanınamaz” demez; yalnız bu k için tanınmadı diyebilir.

Bütçe Olarak Durum Sayısı

İlk model en az şeye sahip olandır. Bir sonlu otomat (finite automaton), girdiyi soldan sağa bir kez okur, okuduğunu saklamaz ve yalnız sonlu sayıda durumdan birinde bulunur. Belleği yoktur; belleğin yerini durum sayısı tutar. Durum makinesinin tanımı Yazılım Mimarisi ve Modelleme ve Gösterim kurslarında kuruldu ve burada tekrarlanmaz; buradaki soru farklıdır: kaç dil tanınabiliyor.

• HM1 — Abece iki simgelidir. Evren, uzunluğu belirli bir sınırı geçmeyen bütün dizilerin (string) sonlu kümesidir ve boş dizi de evrendedir. Uzunluğu 4’ü geçmeyen evren 31 dizi içerir.
• HM2 — Bir dil, evrenin bir alt kümesidir. 31 dizilik evrende yazılabilecek dil sayısı $2^{31}$’dir.
• HM3 — Otomat belirlenimci (deterministic) kurulur: başlangıç durumu 0’dır, geçiş tablosu her durum ile simge ikilisine tek bir durum atar, kabul kümesi durumların bir alt kümesidir. Bir dizi, okunduktan sonra kalınan durum kabul kümesindeyse tanınır.
• HM4 — k durumlu bütün otomatlar sayılabilir: $k^{2k}$ geçiş tablosu ile $2^k$ kabul kümesinin bileşimi. k=1 için 2, k=2 için 64, k=3 için 5832 otomat.
• HM5 — Ölçü tam sayımdır: tahmin yoktur, örnekleme yoktur. Bu kursun hiçbir ölçüsünde random ve time kullanılmaz; ölçülen şey adımdır, süre değil.

Somut bir örnek tanımı yerine oturtur. İki durumlu bir otomat, “şimdiye kadar okunan a sayısı çift mi” sorusunun yanıtını durumunda tutabilir: her a durumu değiştirir, her b durumu olduğu gibi bırakır, kabul kümesi de çift durumudur. Bu otomat girdiyi ne saklar ne geri okur; yine de her uzunluktaki her diziyi doğru sınıflar. Bir dili tanımak budur: dizinin dilde olup olmadığına, sonlu bir bellekle ve tek geçişte karar vermek.

"""Sonlu otomat: k durumlu BUTUN otomatlar sayilir , tanidiklari dil toplanir."""
from itertools import product

ALFABE = ("a", "b")


def diziler(en_uzun):
    cikti = [""]
    for n in range(1, en_uzun + 1):
        cikti += ["".join(d) for d in product(ALFABE, repeat=n)]
    return cikti


def otomat_kos(gecis, kabul, dizi, baslangic=0):
    d = baslangic
    for s in dizi:
        d = gecis[(d, s)]
    return d in kabul


def otomatlar(k):
    """k durumlu butun belirlenimci otomatlar: gecis tablosu x kabul kumesi."""
    hucreler = [(d, s) for d in range(k) for s in ALFABE]
    for hedefler in product(range(k), repeat=len(hucreler)):
        gecis = dict(zip(hucreler, hedefler))
        for kabul_maske in range(1 << k):
            kabul = {i for i in range(k) if kabul_maske >> i & 1}
            yield gecis, kabul


def taninabilen_diller(k, evren):
    """k durumlu otomatlarin evren uzerinde tanidigi AYRI dil sayisi."""
    diller = set()
    for gecis, kabul in otomatlar(k):
        diller.add(frozenset(d for d in evren if otomat_kos(gecis, kabul, d)))
    return diller


E = diziler(4)
print("evren: uzunlugu 4'u gecmeyen dizi sayisi =", len(E))
print("durum  otomat  taninan ayri dil  evrende yazilabilecek dilin orani")
for k in (1, 2, 3):
    diller = taninabilen_diller(k, E)
    print(f"  {k:3d}  {sum(1 for _ in otomatlar(k)):6d}  {len(diller):16d}"
          f"  {len(diller) / 2 ** len(E):.10f}")
print("evrende yazilabilecek butun dil sayisi: 2^31 =", 2 ** 31)

evren: uzunlugu 4'u gecmeyen dizi sayisi = 31
durum  otomat  taninan ayri dil  evrende yazilabilecek dilin orani
    1       2                 2  0.0000000009
    2      64                26  0.0000000121
    3    5832              1054  0.0000004908
evrende yazilabilecek butun dil sayisi: 2^31 = 2147483648

Üç sayı yan yana duruyor. Bütçe: durum sayısı 1, 2, 3 — sırasıyla 2, 64 ve 5832 otomat. Bütçenin yanıtladığı: bu otomatlar 31 dizilik evrende 2, 26 ve 1054 ayrı dili karara bağlıyor. Bütçenin yanıtlayamadığı: geriye $2^{31} - 1054$ dil kalıyor; üç durumlu bütçenin kapsadığı pay 0,0000004908.

Bütçe 5832 otomata çıkarken tanınan dil sayısı 2’den 1054’e, yani 527 katına çıkıyor. Buna karşılık kapsanan pay milyarda birden milyonda yarıma yükseliyor. Model sınıfı büyüyor ve oran hâlâ sıfıra yakın. Dikkat edilecek ikinci nokta 5832 otomatın yalnız 1054 ayrı dil üretmesidir: otomatların çoğu birbirinin kopyasıdır, çünkü ulaşılamayan durumlar ve eşdeğer durumlar aynı dili yeniden yazar.

Bütçe Büyüdükçe Ne Değişiyor

Yukarıdaki oran tek bir evrende ölçüldü ve tek bir evrende ölçülen oran bir sonuç değildir. Bütçe süpürmesi bu kursta zorunludur: her ölçü en az üç bütçe değerinde tekrarlanır ve sonucun bütçeyle değişip değişmediği yazılır. Burada süpürülen ikinci eksen evrenin uzunluk sınırıdır.

• HM6 — Bütçe süpürmesi iki eksende yapılır: durum sayısı ve evrenin uzunluk sınırı. Bir bütçenin yeterliliği ancak ikisi birlikte yazıldığında okunabilir.

"""Butce supurmesi: evren buyudukce ayni durum butcesi ne kadarini kapsiyor."""
from itertools import product

ALFABE = ("a", "b")


def diziler(en_uzun):
    cikti = [""]
    for n in range(1, en_uzun + 1):
        cikti += ["".join(d) for d in product(ALFABE, repeat=n)]
    return cikti


def otomat_kos(gecis, kabul, dizi):
    d = 0
    for s in dizi:
        d = gecis[(d, s)]
    return d in kabul


def otomatlar(k):
    hucreler = [(d, s) for d in range(k) for s in ALFABE]
    for hedefler in product(range(k), repeat=len(hucreler)):
        gecis = dict(zip(hucreler, hedefler))
        for kabul_maske in range(1 << k):
            yield gecis, {i for i in range(k) if kabul_maske >> i & 1}


def taninabilen_diller(k, evren):
    return {frozenset(d for d in evren if otomat_kos(gecis, kabul, d))
            for gecis, kabul in otomatlar(k)}


print("uzunluk  dizi  k=1  k=2   k=3  evrendeki dil  k=3'un kapsadigi pay")
for u in (1, 2, 3, 4):
    E = diziler(u)
    s = [len(taninabilen_diller(k, E)) for k in (1, 2, 3)]
    print(f"{u:7d}  {len(E):4d}  {s[0]:3d}  {s[1]:3d}  {s[2]:4d}"
          f"  {2 ** len(E):13d}  {s[2] / 2 ** len(E):.10f}")

uzunluk  dizi  k=1  k=2   k=3  evrendeki dil  k=3'un kapsadigi pay
      1     3    2    8     8              8  1.0000000000
      2     7    2   26   116            128  0.9062500000
      3    15    2   26   690          32768  0.0210571289
      4    31    2   26  1054     2147483648  0.0000004908

Bu tablo tek başına bir dersin sonucudur. Uzunluk sınırı 1 olan üç dizilik evrende üç durumlu otomatlar her dili tanıyor: kapsanan pay 1,0000000000. Uzunluk 2’de pay 0,9062500000, uzunluk 3’te 0,0210571289, uzunluk 4’te 0,0000004908. Aynı bütçe, aynı model, dört ölçüm — ve “yeterli” ile “hiç” arasındaki bütün yol. Bir bütçenin yeterliliği bütçenin özelliği değil, bütçe ile evrenin ilişkisidir.

İkinci sütun daha da öğreticidir. İki durumlu otomatlar uzunluk 2’de 26 dil tanıyor ve uzunluk 3 ile 4’te hâlâ 26. Evren 7 diziden 31 diziye çıkarken tanınan dil sayısı hiç oynamıyor. Bu doyum bir ölçüm kusuru değil: iki durumla ayırt edilebilecek durum sayısı tükendiği için, evrene eklenen her yeni dizi zaten var olan 26 dilden birine düşüyor. Bütçeyi büyütmek bazen her şeyi değiştirir, bazen hiçbir şeyi; ve hangisi olduğu ancak ölçülerek görülür.

Bir Dili Tanımak İçin Kaç Durum Gerekir

Şimdiye kadar soru “k durum kaç dil tanır” biçimindeydi. Tersi daha kullanışlıdır: verilen bir dil için en az kaç durum gerekir. Bunun aracı artık dildir (residual language): bir önekten sonra hangi kuyrukların diziyi dile soktuğu. İki önek aynı artık dili taşıyorsa hiçbir otomat onları ayırmak zorunda değildir; ayrı artık diller taşıyorlarsa otomat onları ayrı durumlara koymak zorundadır. Ayrı artık dillerin sayısına ayırt edilebilirlik öbeği denir.

• HM7 — Bir önekin artık dili, o önekten sonra eklendiğinde diziyi dile sokan evrendeki kuyrukların kümesidir.
• HM8 — İki öneği ancak iki uzantısı da evrende kalan bir kuyruk ayırabilir. Uzunluk sınırının dışına taşan bir kuyruk otomatı hiçbir şeye zorlamaz.
• HM9 — Tam sayım burada ucuzlatılır: kabul kümeleri ayrıca taranmaz, geçiş tablosu verildiğinde her diziye gereken kabul kararı toplanır ve çelişki çıkmazsa o tablo yeter. Sonuç, kabul kümelerini tek tek denemekle aynıdır.

"""Artik dil , ayirt edilebilirlik obegi ve tam sayim yan yana."""
from itertools import product

ALFABE = ("a", "b")


def diziler(en_uzun):
    cikti = [""]
    for n in range(1, en_uzun + 1):
        cikti += ["".join(d) for d in product(ALFABE, repeat=n)]
    return cikti


def artik_dil(onek, hedef, evren):
    """Onekten sonra hangi kuyruklar dile sokuyor."""
    return frozenset(k for k in evren if onek + k in hedef)


def en_az_durum(hedef, evren):
    """Ortak tanimin araci: ayirt edilebilirlik obeklerinin sayisi."""
    onekler = {d[:i] for d in evren for i in range(len(d) + 1)}
    return len({artik_dil(o, hedef, evren) for o in onekler})


def ayrilan_onek(hedef, evren):
    """Iki onegi ancak IKI uzantisi da evrende kalan bir kuyruk ayirabilir."""
    ev = set(evren)
    onekler = sorted({d[:i] for d in evren for i in range(len(d) + 1)},
                     key=lambda o: (len(o), o))
    imza = {o: tuple((1 if o + k in hedef else 0) if o + k in ev else -1
                     for k in evren) for o in onekler}
    secilen = []
    for o in onekler:
        if all(any(x >= 0 and y >= 0 and x != y
                   for x, y in zip(imza[o], imza[p])) for p in secilen):
            secilen.append(o)
    return len(secilen)


def taniyan_var_mi(k, hedef, evren):
    """k durumlu butun gecis tablolari taranir; kabul kumesi tutarlilikla secilir."""
    hucreler = [(d, s) for d in range(k) for s in ALFABE]
    for hedefler in product(range(k), repeat=len(hucreler)):
        gecis = dict(zip(hucreler, hedefler))
        gerek, tutarli = {}, True
        for dizi in evren:
            d = 0
            for s in dizi:
                d = gecis[(d, s)]
            istenen = dizi in hedef
            if gerek.setdefault(d, istenen) != istenen:
                tutarli = False
                break
        if tutarli:
            return True
    return False


def en_kucuk_k(hedef, evren, ust=5):
    for k in range(1, ust + 1):
        if taniyan_var_mi(k, hedef, evren):
            return k
    return None


def cift_a(d):
    return d.count("a") % 2 == 0


def ab_ile_biten(d):
    return d.endswith("ab")


print("dil            uzunluk  dizi  obek  ayrilan onek  tam sayim")
for ad, olcut in (("a sayisi cift", cift_a), ("ab ile biten ", ab_ile_biten)):
    for u in (2, 3, 4):
        E = diziler(u)
        h = frozenset(d for d in E if olcut(d))
        print(f"{ad}  {u:7d}  {len(E):4d}  {en_az_durum(h, E):4d}"
              f"  {ayrilan_onek(h, E):12d}  {en_kucuk_k(h, E):9d}")

dil            uzunluk  dizi  obek  ayrilan onek  tam sayim
a sayisi cift        2     7     5             2          2
a sayisi cift        3    15     7             2          2
a sayisi cift        4    31     9             2          2
ab ile biten         2     7     4             3          3
ab ile biten         3    15     6             3          3
ab ile biten         4    31     9             3          3

Üç sütun üç ayrı şey söylüyor ve ikisi birbirini düzeltiyor. Öbek sayısı “a sayısı çift” dili için 5, 7, 9 diye büyüyor; oysa tam sayım aynı dili iki durumla tanıyan bir otomatın var olduğunu gösteriyor. Fark evrenin kesiğinden gelir: uzunluk sınırına yaklaşan önekler, kuyrukları evrenin dışına taştığı için yapay olarak ayrılır. Öbek sayısı bir üst sayımdır ve tek başına durum sayısı diye okunamaz. Ayrılan önek sayısı bu kesiği hesaba katar ve altı ölçümün altısında tam sayımla birebir uyuşuyor — bu bir uyuşmadır, bir kanıt değil, ve sınandığı bütçe uzunluk sınırı 4’e kadardır.

Bu düzeltme kursun kuralının kendisine uygulanmasıdır. Öbek sayımı ucuz bir hesaptır ve tam sayım pahalıdır; ucuz hesabın pahalı olanın yerini tutup tutmadığı varsayılmaz, sınanır. Sonraki üç derste de aynı yol izlenir: ucuz ölçü önce yazılır, sonra bir bütçe içinde tam sayımla karşılaştırılır ve ayrıldığı yer saklanmaz.

Düzenli dil kavramı burada tanımla değil ölçüyle kurulur. Bir dil, gereken durum sayısı evren büyüdükçe büyümüyorsa düzenlidir: “a sayısı çift” üç evrende de 2, “ab ile biten” üç evrende de 3. Bu iki dil için sabit bir bütçe seçilebilir ve seçilen bütçe her uzunlukta yeter. Sonraki ders aynı üç ölçüyü bu özelliği taşımayan bir dile uygular.

Özet

• Sonlu otomatın bütçesi durum sayısıdır; k durumlu bütün belirlenimci otomatlar sayılabilir ve k=1, 2, 3 için sırasıyla 2, 64 ve 5832 tanedir.
• Uzunluğu 4’ü geçmeyen 31 dizilik evrende bu otomatlar 2, 26 ve 1054 ayrı dil tanıyor; evrende yazılabilecek dil sayısı 2 üzeri 31 ve üç durumun kapsadığı pay 0,0000004908.
• Bütçe süpürmesi bir bütçenin yeterliliğinin evrene bağlı olduğunu gösteriyor: üç durum, uzunluk sınırı 1’de evrenin tamamını, uzunluk sınırı 4’te milyonda yarımını kapsıyor.
• İki durumlu otomatların tanıdığı dil sayısı uzunluk 2’den sonra 26’da donuyor; evreni büyütmek bu bütçe için hiçbir şey değiştirmiyor.
• Artık dil öbeklerinin sayısı bir üst sayımdır: “a sayısı çift” için 9 öbek çıkarken tam sayım iki durumun yettiğini gösteriyor; ayırt eden kuyruğun iki uzantısı da evrende kalmalıdır.
• Bir dil, gereken durum sayısı evrenle birlikte büyümüyorsa düzenlidir; bu iki dil için üç evrende de sabit kalıyor.

Sonraki Adım

Sonraki ders aynı üç ölçüyü, sayma gerektiren bir dile uygular: eşit sayıda a’nın ardından eşit sayıda b gelen diziler. Sorulacak olan şudur: gereken durum sayısı evrenle birlikte büyürse, bütçeyi büyütmek bir çözüm müdür, yoksa değiştirilmesi gereken şey bütçe değil model sınıfı mıdır. Yanıt, üç satırlık bir üretim kuralının bütün bir otomat ailesinin yapamadığını yapmasıyla gelir.