--- title: 'Bağlamdan Bağımsız Diller' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/baglamdan-bagimsiz-diller' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:31+00:00' license: 'CC BY-SA 4.0' --- # Bağlamdan Bağımsız Diller Durum bütçesinin yetmediği dillerin ölçülmesi: eşit sayıda a ve b dizisi için gereken durum sayısı uzunluk sınırıyla 3, 5, 7, 9, 11 diye büyürken tek satırlık bir üretim kuralı aynı dili tam olarak üretiyor ve kuralın betimi hiç büyümüyor. Önceki ders bir dili düzenli sayan ölçüyü kurdu: gereken durum sayısı evren büyüdükçe büyümüyorsa o dil için sabit bir bütçe seçilebilir. İki örnek bu ölçüyü geçti; "a sayısı çift" üç evrende de 2, "ab ile biten" üç evrende de 3 durum istedi. Şimdi ölçüyü geçmeyen bir dile bakılır. Sorulacak dil şudur: önce bir miktar a, sonra **tam olarak aynı sayıda** b. Bu dil bir sayma işi ister; okunan a sayısı, b'lerin sayılabilmesi için bir yerde tutulmak zorundadır. Sonlu otomatın tek belleği durumudur, ve durum sayısı sabittir. Sorunun bütün ağırlığı buradadır. ## Sayma Gerektiren Bir Dil Önceki dersin üç ölçüsü aynen kullanılır: artık dil öbeklerinin sayısı, ayrılan önek sayısı ve tam sayım. Üçü de aynı evrende çalıştırılır, sonra evren süpürülür. Yanına ikinci bir dil konur: **dengeli dizi**, yani a'nın açtığı ve b'nin kapattığı sayılırsa hiçbir önekte kapanışın açılışı geçmediği ve sonda eşitlendiği dizi. - **HM10** — Hedef dil `esit_sayida`, yani bir dizinin ilk yarısı yalnız a, ikinci yarısı yalnız b ise ve uzunluk çiftse dile aittir. Boş dizi dile aittir. - **HM11** — İkinci hedef `dengeli`, tek bir sayaçla sınanır: a sayacı bir artırır, b bir azaltır; sayaç hiçbir noktada eksiye düşmez ve sonda sıfırdır. - **HM12** — Tam sayım bu derste k=1'den 5'e kadar yapılır. Beş durumlu geçiş tablosu sayısı $5^{10}$'dur; ölçünün bütçesi budur ve k=6 bu derste denenmedi. - **HM13** — Ölçüm hiçbir yerde "bu dil tanınamaz" demez. Söyleyebileceği tek şey, denenen k değerleri ve denenen uzunluk sınırları içinde ne bulunduğudur. ```python """a^n b^n ve dengeli dil: obek , ayrilan onek 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 esit_sayida(d): """a^n b^n biciminde mi.""" n = len(d) if n % 2: return False yari = n // 2 return d[:yari] == "a" * yari and d[yari:] == "b" * yari def dengeli(d): """a acar , b kapatir; hicbir onekte kapanis acilisi gecmez.""" sayac = 0 for s in d: sayac += 1 if s == "a" else -1 if sayac < 0: return False return sayac == 0 def en_az_durum(hedef, evren): """Ayirt edilebilirlik obekleri: artik dillerin sayisi.""" onekler = {d[:i] for d in evren for i in range(len(d) + 1)} return len({frozenset(k for k in evren if o + k in hedef) 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; 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 print("uzunluk dizi a^n b^n: obek onek dengeli: obek onek") for u in (2, 4, 6, 8, 10): E = diziler(u) h1 = frozenset(d for d in E if esit_sayida(d)) h2 = frozenset(d for d in E if dengeli(d)) print(f"{u:7d} {len(E):5d} {en_az_durum(h1, E):12d} {ayrilan_onek(h1, E):4d}" f" {en_az_durum(h2, E):14d} {ayrilan_onek(h2, E):4d}") print() print("tam sayim: k = 1..5 icin BUTUN otomatlar denendi") print("uzunluk a^n b^n hedefi taniyan en kucuk k") for u in (2, 3, 4): E = diziler(u) h = frozenset(d for d in E if esit_sayida(d)) k = [i for i in (1, 2, 3, 4, 5) if taniyan_var_mi(i, h, E)] print(f"{u:7d} {str(sorted(h)):28s} {k[0] if k else 'yok'}") ``` ``` uzunluk dizi a^n b^n: obek onek dengeli: obek onek 2 7 4 3 4 3 4 31 6 5 7 4 6 127 8 7 11 5 8 511 10 9 16 6 10 2047 12 11 22 7 tam sayim: k = 1..5 icin BUTUN otomatlar denendi uzunluk a^n b^n hedefi taniyan en kucuk k 2 ['', 'ab'] 3 3 ['', 'ab'] 3 4 ['', 'aabb', 'ab'] 5 ``` Üç sayı yan yana. **Bütçe:** durum sayısı 1'den 5'e, uzunluk sınırı 2'den 10'a. **Bütçenin yanıtladığı:** gereken durum sayısı a'lı b'li dilde **3, 5, 7, 9, 11** diye, dengeli dilde **3, 4, 5, 6, 7** diye büyüyor; uzunluk 4 evreninde tam sayım en küçük k'yı **5** buluyor ve bu, ayrılan önek sayısıyla birebir aynı. **Bütçenin yanıtlayamadığı:** sabit bir k'nın **hiçbir** uzunlukta yetmediği. Ölçüm bunu söyleyemez; söyleyebildiği şey denenen beş uzunluk ve beş k değeri içinde durum sayısının durmadan büyüdüğüdür. Büyümenin nedeni ölçümde değil dildedir. Önce yalnız a'dan oluşan önekler düşünülsün: iki ayrı önek olan `a` ile `aa`, `b` kuyruğuyla ayrılır, çünkü `ab` dile aittir ve `aab` ait değildir; üstelik iki uzantı da evrenin içindedir. Aynı şey `aa` ile `aaa` için `bb` kuyruğuyla, `aaa` ile `aaaa` için `bbb` kuyruğuyla geçerlidir. Uzunluk sınırı 2m olan bir evrende bu zincir m+1 öneğe kadar uzar ve zincirdeki her önek ayrı bir durum ister. Sınır büyüdükçe zincir uzar. Buradaki cümle kesinlikle şudur: **her sabit k için, o k'nın yetmediği bir uzunluk ölçüldü**; "her zaman yetmez" cümlesi kuramın sonucudur ve koşumla kurulmaz. Tam sayım tablosunun ilk iki satırı da okunmalıdır. Uzunluk 2 ile 3 evreninde hedef aynı kalıyor, çünkü tek sayı uzunluklu hiçbir dizi dile ait değil; en küçük k ikisinde de 3. Uzunluk 4'te hedefe `aabb` girer girmez sayı **5'e sıçrıyor**. Yani gereken durum, evrene eklenen dizi sayısıyla değil, dile **yeni bir sayma derinliği** eklenmesiyle artıyor. İki durumlu otomatın hafızası bir bitti; burada gereken şey, kaç a okunduğunu tutan bir sayaçtır ve sayacın alacağı değer sayısı uzunlukla birlikte artar. Öbek sütunu ile önek sütunu arasındaki bir birimlik fark önceki dersteki üst sayımın sürdüğünü gösteriyor: a'lı b'li dilde öbek 4, 6, 8, 10, 12 iken ayrılan önek 3, 5, 7, 9, 11. İki sütunun **eğimi** aynı; ikisi de doğrusal büyüyor. Dengeli dilde ise iki sütun ayrışıyor, öbek 22'ye çıkarken önek 7'de kalıyor — ucuz ölçü ile sınanmış ölçü arasındaki fark, dile göre değişiyor ve bu yüzden ucuz ölçü tek başına yazılmaz. ## Üretim Kuralı Otomatın Yapamadığını Yapıyor Bütçeyi büyütmek bir yol. İkinci yol modeli değiştirmektir. **Üretim kuralı (production rule)**, bir simgeyi bir diziyle değiştirmeye izin veren kuraldır; kuralların art arda uygulanmasına **türetme (derivation)** denir. Bir dilin bütün dizileri sonlu bir kural kümesinden türetilebiliyorsa o dile **bağlamdan bağımsız dil (context-free language)** denir. Dilbilgisi ve ayrıştırma Bilgisayarlar Nasıl Çalışır kursundaki Derleme Aşamaları dersinde kuruldu; sözcük birimleri, soyut sözdizim ağacı ve işleç önceliğinin ağaca gömülmesi orada anlatıldı ve burada tekrarlanmaz. Bu dersin eklediği tek şey ölçüdür: kuralın ürettiği küme ile hedef dilin **birebir aynı** olup olmadığı. - **HM14** — Kural `S -> a S b | boş` iki seçenek taşır ve tek satırdır. Türetme derinliği, kuralın kaç kez uygulandığıdır. - **HM15** — İkinci kural `S -> a S b S | boş`, dengeli dizileri üretir. Ölçüm, üretilen küme ile evrendeki dengeli dizilerin kümesinin eşit olup olmadığıdır; alt küme yetmez. - **HM16** — Kuralın **betimi** ile **koşumu** ayrı ölçülür: betim satır sayısı, koşum türetme derinliğidir. ```python """Uretim kurali: betim sabit kalir , turetme derinligi girdiyle buyur.""" from itertools import product ALFABE = ("a", "b") KURAL = {"S": [("a", "S", "b"), ()]} # S -> a S b | bos 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 esit_sayida(d): n = len(d) if n % 2: return False yari = n // 2 return d[:yari] == "a" * yari and d[yari:] == "b" * yari def dengeli(d): sayac = 0 for s in d: sayac += 1 if s == "a" else -1 if sayac < 0: return False return sayac == 0 def turet(en_derin): """Kuraldan en cok `en_derin` adimda uretilen diziler.""" uretilen = {""} onceki = {""} for _ in range(en_derin): yeni = {"a" + d + "b" for d in onceki} uretilen |= yeni onceki = yeni return uretilen def turet_dengeli(en_uzun): """S -> a S b S | bos ; uzunlugu en_uzun'u gecmeyen butun turetmeler.""" kume, degisti = {""}, True while degisti: degisti = False for x in list(kume): for y in list(kume): yeni = "a" + x + "b" + y if len(yeni) <= en_uzun and yeni not in kume: kume.add(yeni) degisti = True return kume print("S -> a S b | bos") print("derinlik uretilen en uzun ayni uzunluktaki hedefi kapsiyor mu") for d in (1, 2, 3, 4, 5): U = turet(d) hedef = {x for x in diziler(2 * d) if esit_sayida(x)} print(f"{d:8d} {len(U):8d} {max(len(x) for x in U):7d} {hedef <= U}") print(" 3 adimda uretilenler:", sorted(turet(3))) print() print("S -> a S b S | bos") print("uzunluk turetilen dengeli dizi ikisi ayni mi") for u in (2, 4, 6, 8): T = turet_dengeli(u) D = {x for x in diziler(u) if dengeli(x)} print(f"{u:7d} {len(T):9d} {len(D):12d} {T == D}") ``` ``` S -> a S b | bos derinlik uretilen en uzun ayni uzunluktaki hedefi kapsiyor mu 1 2 2 True 2 3 4 True 3 4 6 True 4 5 8 True 5 6 10 True 3 adimda uretilenler: ['', 'aaabbb', 'aabb', 'ab'] S -> a S b S | bos uzunluk turetilen dengeli dizi ikisi ayni mi 2 2 2 True 4 4 4 True 6 9 9 True 8 23 23 True ``` Tek satırlık kural üç türetme adımında `""`, `ab`, `aabb`, `aaabbb` üretiyor; bu, uzunluğu 6'yı geçmeyen evrendeki a'lı b'li dizilerin **tamamıdır**. Beş derinlikte uzunluk 10'a kadar aynı sonuç sürüyor: kapsama sütunu beş satırda da `True`. İkinci kural için ölçü daha sıkıdır, çünkü alt küme değil **eşitlik** sınanıyor: uzunluk 8'e kadar üretilen 23 dizi, evrendeki 23 dengeli dizinin aynısı. Bu, önceki bölümün ölçtüğü şeyin karşıtıdır. Aynı dil için otomatın istediği durum sayısı 3'ten 11'e çıkarken, kuralın satır sayısı **1'de kaldı**. Model sınıfını değiştirmek, bütçeyi büyütmekten **başka bir şeydir**: birincisi betimin boyunu sabit tutar, ikincisi betimi büyütür. ## Bütçe Nereye Konuyor İki modelin ödediği bedel aynı yerde durmuyor. Aşağıdaki tablo iki bölümün sayılarını yan yana koyar; durum sütunu ayrılan önek sayısından, derinlik sütunu türetme ölçümünden gelir. | Uzunluk sınırı | Otomat: gereken durum | Kural: satır | Kural: türetme derinliği | |---|---|---|---| | 2 | 3 | 1 | 1 | | 4 | 5 | 1 | 2 | | 6 | 7 | 1 | 3 | | 8 | 9 | 1 | 4 | | 10 | 11 | 1 | 5 | Otomatta büyüyen şey **betimdir**: daha uzun diziler için daha büyük bir makine yazılmak zorundadır ve makinenin kendisi girdiyle birlikte büyür. Kuralda büyüyen şey **koşumdur**: kural aynı kalır, yalnız daha çok kez uygulanır. Bir modelin gücünü ölçerken sorulacak soru "kaç adım harcıyor" değil, **"girdiyle birlikte ne büyüyor"** olmalıdır. Bu ayrımın bir bedeli de var ve saklanmaz. Kural, dizinin dile ait olup olmadığına sonlu otomatın tek geçişiyle karar vermez; türetmeyi araması gerekir, ve arama tek geçişten pahalıdır. Ölçüm bunu da gösteriyor: dengeli dil için uzunluk 8'e kadar 23 dizi üretmek, kümenin sabit noktaya oturmasına kadar yinelemeyi sürdürmeyi gerektirdi. Güç bedava gelmiyor; ödenen şey betim boyu yerine arama. ## Özet - Eşit sayıda a ve b isteyen dilde gereken durum sayısı uzunluk sınırıyla birlikte 3, 5, 7, 9, 11 diye büyüyor; dengeli dilde 3, 4, 5, 6, 7 diye. - Uzunluk 4 evreninde k=1'den 5'e kadar bütün otomatlar denendi ve en küçük k **5** çıktı; bu sayı ayrılan önek ölçüsüyle birebir aynı. - Sabit bir k'nın hiçbir uzunlukta yetmediği ölçülmedi ve ölçülemez; ölçülen şey her denenen k için o k'nın yetmediği bir uzunluğun bulunmasıdır. - Tek satırlık `S -> a S b | boş` kuralı üç türetme adımında uzunluğu 6'yı geçmeyen bütün hedef dizileri üretiyor; `S -> a S b S | boş` kuralı uzunluk 8'e kadar 23 dengeli dizinin tamamını, fazlasız üretiyor. - Otomatta girdiyle birlikte büyüyen şey betim, üretim kuralında koşumdur; model sınıfını değiştirmek bütçeyi büyütmekten başka bir şeydir. - Gücün bedeli de ölçüldü: kural tek geçişte karar vermez, türetmeyi arar; kazanılan betim boyu, ödenen arama. ## Sonraki Adım İki model de bir sınırla tanımlandı: biri durum sayısıyla, öteki kural biçimiyle. Sonraki ders sınırı olabildiğince gevşetir ve okunan simgeyi **değiştirebilen**, ileri geri gezinebilen bir şeride sahip bir model kurar. Sorulacak soru şudur: bu modelin bütün üyelerini tek tek sayabilir miyiz, ve saydığımızda kaçının durduğunu bir adım bütçesiyle öğrenebilir miyiz. Yanıtın ilk yarısı beklenenden kolay, ikinci yarısı beklenenden zordur.