--- title: 'Sonlu Otomatlar' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/sonlu-otomatlar' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:32+00:00' license: 'CC BY-SA 4.0' --- # Sonlu Otomatlar Durum bütçesinin tam sayımla ölçülmesi: 31 dizilik evrende 1 durumlu otomatlar 2, 2 durumlu 26, 3 durumlu 1054 ayrı dil tanıyor; evrende yazılabilecek 2 üzeri 31 dilin yanında bu, 0,0000004908'lik bir paydır. İ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 **durum**dan 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. ```python """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. ```python """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. ```python """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.