Bağlamdan Bağımsız Diller

Ö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.

"""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.

"""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.