Chomsky Hiyerarşisi, Noam Chomsky'nin 1956'ya yayımladığı çalışmalarıyla, dilin rastgele gözlemlenen sözcük dizileri yerine, bu dizileri üreten kural sistemleri üzerinden çözümlenebileceği fikriyle öne sürülmüştür.

Biçimsel Dil Teorisi (Formal Language Theory - FLT), 20. yüzyılın ortalarında Noam Chomsky’nin öncülük ettiği dilbilimsel paradigma değişiminin temel taşlarından biridir. Alan Turing’in hesaplanabilirlik kuramı ve Axel Thue, Emil Post gibi öncüllerin temel yaklaşımlarından beslenen bu teori, dilin yapısını biçimsel, matematiksel kavramlarla ifade etmeyi amaçlamaktadır. Bu yaklaşım, dilbilim çalışmalarının nesnesini cümlelerden ve gözlemlerden, kurallara ve türetim süreçlerine kaydırmış, modern dilbilimin yanı sıra teorik bilgisayar bilimi, yapay zeka ve hesaplamalı biyoloji gibi alanlara da doğrudan yön vermiştir.

Chomsky’nin hiyerarşik sınıflandırması, bir dilin yapısal karmaşıklığını belirlemenin ve bunu ölçmenin sistematik bir yolunu sunar. Bu bağlamda, gramerler yalnızca dilin gözlemlenen düzenliliklerinin bir özeti değil; aksine, bu düzenlilikleri üreten zihinsel modellerin matematiksel karşılığıdır. Böylece Chomsky Hiyerarşisi, biçimsel gramerlerin tanımlanabilirlik gücünü sınırlayan veya genişleten üretim kurallarına dayalı olarak dört temel seviyeye ayrılır.

Temel Kavramlar: Alfabe, Dil ve Gramer

Biçimsel dil kuramında temel kavramlar oldukça belirgindir. Alfabe (Σ), üzerinde işlem yapılan sonlu semboller kümesidir. Bu sembollerin belirli bir düzenle sıralanmasıyla string veya dizge oluşur. Bir dil, bu dizgelerin (stringlerin) belirli bir kümesidir ve bu küme sonlu ya da sonsuz olabilir.

Bir dilin üretimi, gramer (grammar) aracılığıyla gerçekleştirilir. Bir gramer, dört unsurdan oluşur: terminal semboller kümesi (Σ), non-terminal semboller kümesi (NT), başlangıç sembolü (S) ve üretim kuralları kümesi (R). Her bir üretim kuralı, α → β biçiminde tanımlanır ve bir dizge içinde α alt dizgesi β ile değiştirilebilir. Bu değişim işlemleri, türetim (derivation) sürecini oluşturur.

Biçimsel olarak tanımlanan bir gramer G, G = ⟨Σ, NT, S, R⟩ şeklinde ifade edilir. Başlangıç sembolünden başlanarak yalnızca terminal sembollerden oluşan bir dizgeye ulaşılabiliyorsa, bu dizge ilgili gramer tarafından üretilmiş kabul edilir. Bu sürecin sonunda elde edilen dizgelerin kümesine dilin kendisi, yani L(G) adı verilir.

Chomsky Hiyerarşisinin Yapısı

Chomsky Hiyerarşisi, biçimsel gramerlerin ifade gücünü belirleyen dört ana düzeyi içerir:

Tip-0 Gramerler (Sınırsız Gramerler)

Bu en geniş sınıf, üzerinde herhangi bir kısıtlama olmayan tüm biçimsel gramerleri kapsar. Üretim kuralları, α → β biçimindedir ve α en az bir non-terminal içerir. Tip-0 gramerler, Turing makineleri tarafından tanınabilir dilleri üretir ve bu diller özyinelemeli sayılabilir (recursively enumerable) olarak adlandırılır.

Tip-1 Gramerler (Bağlam-Duyarlı Gramerler)

Bu gramerlerde, üretim kuralları α → β biçiminde tanımlanır ve |α| ≤ |β| kuralına uymak zorundadır. Yani, türetme sırasında stringin uzunluğu kısalmaz. Bu özellik, türetim sürecinin sonlu adımda sonlanmasını garantiler. Tip-1 gramerler, lineer sınırlı otomatlar tarafından tanınır.

Tip-2 Gramerler (Bağlamdan Bağımsız Gramerler)

Bu sınıfta tüm kurallar A → β biçimindedir. Burada A bir non-terminal, β ise terminal ve/veya non-terminal sembollerden oluşan herhangi bir stringdir. Bağlamdan bağımsız gramerler, pushdown automatonlarla ilişkilidir ve programlama dillerinin sözdizimsel analizi bu yapı üzerine kuruludur.

Tip-3 Gramerler (Düzenli Gramerler)

En dar kapsamlı sınıf, düzenli dilleri tanımlar. Kurallar A → aB veya A → a biçimindedir. Tip-3 gramerler, finite state automatonlarla eşlenir ve düzenli ifadeler, bu tür gramerlerin pratik uygulamasıdır.

^{Chomsky Hiyerarşisi Yapısı (Yapay zeka ile oluşturulmuştur.)}

Her bir üst düzey, kendinden sonraki tüm seviyeleri kapsar. Bu kapsayıcılık, düzenli dillerin bağlamdan bağımsız dil olabileceğini, ancak her bağlamdan bağımsız dilin düzenli olamayacağını ifade eder.

Otomatlar ile İlişki

Chomsky Hiyerarşisi, her bir gramer tipine karşılık gelen hesaplama modelini de belirler.

• Tip-0 gramerler Turing makineleri tarafından tanınır. Turing makineleri, sınırsız hafızaya sahip kuramsal hesaplama aygıtlarıdır ve tüm hesaplanabilir problemleri simgeler.
• Tip-1 gramerler, lineer sınırlı otomatlar (linear bounded automata) ile ilişkilidir. Bu makineler, Turing makinelerine benzer ancak bellekleri giriş uzunluğu ile orantılıdır.
• Tip-2 gramerler, itilebilen yığıt otomatları (pushdown automata) ile tanımlanır. Bu makineler, yığıt kullanarak iç içe yapıları tanıyabilir.
• Tip-3 gramerler, sonlu durum makineleri (finite state automata) ile tanımlanır. Belleği yoktur; mevcut duruma ve giriş sembolüne göre geçiş yaparlar.

Bu otomatlar, dillerin tanınırlığı ve türetilebilirliğinin algoritmik boyutunu temsil eder.

Yer Değiştirilebilirlik (Intersubstitutability) ve Üretkenlik

Biçimsel Dil Teorisi, yalnızca sembollerin dizilişini değil, bu sembollerin sınıflandırılmasını da içerir. Yer değiştirilebilirlik, bir dilde belirli alt ifadelerin aynı kategoride yer alarak birbirlerinin yerine geçebilme yeteneğidir. Örneğin “kedi” ve “köpek” kelimelerinin aynı bağlamda kullanılabilir olması, bu iki kelimenin aynı kategoriye ait olduğunu gösterir.

Bu özellik, gramerlerin sınırlı sayıda kural ile sonsuz sayıda ifade türetebilmesini sağlar. Eğer her ifade ayrı ayrı depolansaydı, sistem sonsuz sayıda ifadeyi tanımlamak için sonsuz kurala ihtiyaç duyardı. Öte yandan, her şeyi unutmak, yani tüm ifadeleri yer değiştirilebilir kılmak, anlamı yok eder. Bu denge, gramerlerin üretkenliğinin temelini oluşturur.

Chomsky Hiyerarşisinin Genişlemeleri

Doğal dillerin bazı karmaşık yapıları, klasik Chomsky Hiyerarşisi’nin sınırlarını aşar. Bu nedenle, Mildly Context-Sensitive Languages (Hafif Bağlam-Duyarlı Diller) kavramı geliştirilmiştir. Tree-Adjoining Grammars (TAG), Multiple Context-Free Grammars (MCFG) ve Minimalist Grammars (MG) gibi genişletilmiş modeller, bağlamdan bağımsız gramerlerin yetmediği çapraz bağımlılık gibi dilsel örüntüleri tanımlamak için kullanılır.

Örneğin İsviçre Almancası’ndaki çapraz bağımlılık örnekleri, klasik CFG ile betimlenemez; bu tür yapılar, bağlam-duyarlılık ve ileri düzey gramer modelleri gerektirir.

Doğal Diller ve Programlama Dilleri Bağlamı

Doğal diller, genellikle bağlamdan bağımsız gramer düzeyindedir; çünkü iç içe geçmiş ifadeler ve öbek yapıları gerektirir. Ancak bazı dil özellikleri bağlam-duyarlılık talep eder. Örneğin, Hollandaca veya İsviçre Almancası, çapraz bağımlılıklar içerir.

Programlama dilleri ise hem düzenli hem de bağlamdan bağımsız yapılara dayanır. Lexical analysis aşaması, düzenli ifadelerle gerçekleştirilirken, sözdizimsel analiz CFG temellidir. Backus-Naur Formu (BNF) bu yapıyı ifade etmenin standart yöntemidir.

Chomsky Hiyerarşisinin Önemi

Chomsky Hiyerarşisi, biçimsel gramerlerin ifade gücünü derecelendirerek dilin matematiksel analizine sistematik bir temel sunar. Bu hiyerarşi sayesinde, dil modelleri için gereken hesaplama gücü, gramer kısıtları ve tanınırlık sınırları açıkça belirlenebilir. Hem dilbilim hem de teorik bilgisayar bilimi açısından, gramerlerin ifade gücü, otomatlar kuramı ile iç içe geçerek modern NLP yaklaşımlarının ve programlama dillerinin temelini oluşturur.

Chomsky’nin ortaya koyduğu bu yapı, dilin üretkenliğini anlamak için vazgeçilmez bir ölçüt haline gelmiş, teorik sınırları ortaya koymakla kalmamış, uygulamalı alanlarda da yeni çözüm yolları yaratmıştır.