Chomsky Hiyerarşisi
Chomsky hiyerarşisi, biçimsel dilleri dört iç içe geçmiş sınıfa ayırmaktadır. Bu sınıfların her biri, dilbilgisi kurallarına getirilen bir kısıtlama ile tanımlanmakta ve belirli bir soyut makine türüyle eşleştirilmektedir.
Tanım
Chomsky hiyerarşisi, biçimsel dilbilgilerinin üretim kurallarına giderek daha güçlü kısıtlamalar getirilerek yapılan bir sınıflandırmadır. Bu sınıflandırma, düzenli, bağlamdan bağımsız, bağlama duyarlı ve özyinelemeli sayılabilir dil sınıflarını katı içermeler zinciri halinde ortaya koymaktadır.
Kapsam
Bu konu, dört dilbilgisi türünü (kısıtlanmamış, bağlama duyarlı, bağlamdan bağımsız ve düzenli), bunların katı kapsamasını ve her seviyeye karşılık gelen otomat modellerini (Turing makinesi, doğrusal sınırlı otomat, yığın otomatı ve sonlu otomat) ele almaktadır. Ayrıca, seviyeleri ayıran kapanış ve karar verilebilirlik özellikleri de incelenmektedir.
Temel sorular
- Dilbilgisi kurallarına getirilen kısıtlamalar, bellek ve işlem gücü üzerindeki sınırlamalara nasıl dönüşmektedir?
- Hiyerarşinin her seviyesi neden bir sonraki seviye tarafından katı bir şekilde içerilmektedir?
- Her dilbilgisi türüne hangi otomat modeli karşılık gelmektedir?
- Hiyerarşide yukarı doğru çıkıldıkça karar verilebilirlik ve kapanış özellikleri nasıl değişmektedir?
Temel kuramlar
- Dilbilgisi-Makine Karşılığı
- Her dilbilgisi sınıfı belirli bir makine modeli tarafından tanınmaktadır — düzenli diller sonlu otomatlar, bağlamdan bağımsız diller yığın otomatları, bağlama duyarlı diller doğrusal sınırlı otomatlar ve kısıtlanmamış diller Turing makineleri tarafından tanınmaktadır. Bu durum, hesaplamanın üretken ve operasyonel tanımlarını birbirine bağlamaktadır.
- Dil Sınıflarının Katı İçermesi
- Her seviye, somut ayırıcı dillerle kanıtlandığı üzere, altındaki seviyeyi doğru bir şekilde içermektedir. Bu nedenle hiyerarşi, eşdeğer tanımlar topluluğu olmaktan ziyade, artan ifade gücünün gerçek bir merdivenidir.
Klinik önem
Bu hiyerarşi, biçimsel dil kuramının düzenleyici haritası niteliğindedir: programlama dilleri, sorgu dilleri ve protokol spesifikasyonları tasarlayanlara, belirli bir örüntü sınıfının ne kadar mekanizma gerektirdiğini bildirmekte ve neyin karar verilebilir neyin ise yalnızca tanınabilir olduğu arasındaki sınırı belirlemektedir.
Tarihçe
Chomsky, hiyerarşiyi 1950'lerin sonlarında doğal dil sözdiziminin biçimsel modellerini ararken önermiştir. Makine karşılıkları ise 1960'lar boyunca otomat kuramının olgunlaşmasıyla belirlenmiş; doğrusal sınırlı otomatlar Myhill tarafından tanıtılmış ve bağlama duyarlı seviye Kuroda tarafından açıklığa kavuşturulmuştur.
Öne çıkan isimler
- Noam Chomsky
- Marcel-Paul Schützenberger
- John Myhill
İlgili konular
Temel eserler
- hopcroft2006
- sipser2013
Sıkça sorulan sorular
- Chomsky hiyerarşisinin dört seviyesi nelerdir?
- En az güçlüden en güçlüye doğru sırasıyla düzenli diller (Tip 3), bağlamdan bağımsız diller (Tip 2), bağlama duyarlı diller (Tip 1) ve özyinelemeli sayılabilir dillerdir (Tip 0). Her seviye, dilbilgisi kurallarına getirilen kısıtlamaları gevşetmekte ve daha fazla belleğe sahip bir makineye karşılık gelmektedir.
- Doğal dil Chomsky hiyerarşisi tarafından kapsanmakta mıdır?
- Hiyerarşi başlangıçta dilbilim tarafından motive edilmiş olsa da, çoğu dilbilimci doğal dillerin bağlamdan bağımsız olmadığı, genellikle hafif bağlama duyarlı olarak adlandırılan bir seviyede yer aldığı sonucuna varmaktadır. İnsan dili bu hiyerarşiye yalnızca gevşek bir şekilde uysa da, hiyerarşi bilgisayar bilimlerinde temel bir konumunu korumaktadır.