Biçimsel Dil Kuramı ve Otomatlar
Biçimsel diller kuramı ve onları tanıyan soyut makineler, dilsel bir örüntünün ne kadar karmaşık olduğunu ve hangi algoritmaların onu işleyebileceğini tanımlamak için bir söz dağarcığı sağlamaktadır.
Tanım
Biçimsel dil kuramı, gramerler tarafından tanımlanan dizeler kümelerini incelerken, otomat kuramı bu kümelerdeki üyeliğe karar veren soyut makineleri incelemektedir.
Kapsam
Chomsky hiyerarşisini (düzenli, bağlamdan bağımsız, bağlama duyarlı, özyinelemeli sayılabilir diller), ilgili gramerleri ve tanıyan otomatları — finite-state machines, pushdown automata ve Turing machines — kapsamaktadır. Dil işleme ile ilgili kapanım ve karar verilebilirlik özelliklerini ve doğal dilin hiyerarşide nerede konumlandığı sorusunu ele almaktadır. Pumping lemaları ve tam karmaşıklık ispatları birincil içerik yerine arka plan bilgisi olarak ele alınmaktadır.
Temel sorular
- Chomsky hiyerarşisinin her seviyesine hangi otomat karşılık gelmektedir?
- Doğal dil hiyerarşide nerede yer almaktadır ve neden bağlamdan bağımsız gücü aştığı iddia edilmektedir?
- Bir dil sınıfının bir işlem altında kapalı olması ne anlama gelmektedir ve bu mühendislik için neden önemlidir?
Anahtar kavramlar
- düzenli dil
- bağlamdan bağımsız gramer
- bağlama duyarlı gramer
- sonlu durum otomati
- yığın otomati
- Turing makinesi
- kapanım özellikleri
- hafif bağlama duyarlılık
Temel kuramlar
- Chomsky hiyerarşisi
- Her biri kısıtlı bir gramer tipi tarafından üretilen ve ilgili bir otomat tarafından tanınan, iç içe geçmiş dört biçimsel dil sınıfı olup, dilsel yapıları gereken hesaplama gücüne göre sıralamaktadır.
- Gramer-otomat yazışması
- Her gramer sınıfı, bir makine sınıfına kanıtlanabilir şekilde eşdeğerdir — düzenli gramerler sonlu otomatlara, bağlamdan bağımsız gramerler yığın otomatlarına — üretici tanımlamaları tanıma algoritmalarına bağlamaktadır.
Tarihçe
Chomsky'nin 1956 tarihli makalesi, sonlu durum modellerinin doğal dil için yetersiz olduğu argümanının bir parçası olarak hiyerarşiyi tanıtmıştır. Sonraki on yıllar otomat yazışmalarını biçimselleştirmiş ve hesaplamalı dilbilimciler daha sonra doğal dilin en fazla 'hafif bağlama duyarlı' (mildly context-sensitive) güce ihtiyaç duyduğunu göstererek, bağlamdan bağımsızın ötesinde gramer biçimselliklerini motive etmiştir.
Tartışmalar
- Doğal dil bağlamdan bağımsız mıdır?
- İsviçre Almancası gibi dillerdeki çapraz-seri bağımlılıklar, doğal dilin bağlamdan bağımsız gücü aştığını savunmak için kullanılmış ve bu durum, doğru ifade gücü seviyesi olarak hafif bağlama duyarlılık (mild context-sensitivity) kavramına yol açmıştır.
Öne çıkan isimler
- Noam Chomsky
- John Hopcroft
- Jeffrey Ullman
- Stephen Kleene
İlgili konular
Temel eserler
- chomsky1956
- hopcroft2006
Sıkça sorulan sorular
- Düzenli bir dil ile bağlamdan bağımsız bir dil arasındaki fark nedir?
- Düzenli diller, sonlu bir otomat tarafından sonlu bellek ile tanınabilmektedir; bağlamdan bağımsız diller ise, dengeli parantezler veya gömülü yan tümceler gibi iç içe geçmiş yapıları izlemek için bir yığına (bir pushdown automaton) ihtiyaç duyabilmektedir.