Otomatlar ve Biçimsel Diller
Otomatlar ve biçimsel diller kuramı, artan güce sahip idealleştirilmiş makineleri ve her birinin tanıyabileceği dizeler veya diller sınıflarını incelemektedir; bu sayede bir örüntünün ne anlama geldiği ve onu tespit etmek için nelerin gerektiği hakkında kesin bir matematiksel açıklama sunulmaktadır.
Tanım
Biçimsel bir dil, sabit bir alfabe üzerindeki sonlu dizeler kümesidir ve bir otomat, kabul eden hesaplamaları böyle bir dili tanımlayan soyut bir hesaplama cihazıdır; bu alan, dilleri onları üreten veya tanıyan en basit otomat veya gramer türüne göre sınıflandırmaktadır.
Kapsam
Bu alan, sonlu otomatları ve düzenli dilleri, yığın otomatlarını ve bağlamdan bağımsız dilleri, gramerleri makine modelleriyle ilişkilendiren Chomsky hiyerarşisini, dil sınıflarının kapanış ve karar özelliklerini ve sonsuz kelimeleri ve ağaçları işleyen otomatları, bunlara eşlik eden cebirsel ve mantıksal karakterizasyonlarla birlikte kapsamaktadır.
Alt konular
Temel sorular
- Sonlu belleğe sahip bir makine hangi dilleri tanıyabilir ve hangi dilleri tanıyamaz?
- Chomsky hiyerarşisinin seviyeleri arasında gramerler ve makine modelleri nasıl bir karşılık gelmektedir?
- Bir dil sınıfı hakkındaki boşluk veya denklik gibi soruların hangileri algoritmik olarak karar verilebilirdir?
- Otomatlar sonsuz kelimelere ve ağaçlara nasıl genişletilmektedir ve bu, doğrulama için neden önemlidir?
Temel kuramlar
- Deterministik ve Deterministik Olmayan Sonlu Otomatların Denkliği
- Her deterministik olmayan sonlu otomat, alt küme yapısı (subset construction) ile aynı dili kabul eden deterministik bir otomata dönüştürülebilmektedir; bu nedenle, deterministik olmama durumu, üstel olarak daha özlü olabilse de, sonlu durum seviyesinde tanıma gücüne ek bir katkı sağlamamaktadır.
- Kleene Teoremi
- Sonlu otomatlar tarafından tanınan diller, düzenli ifadelerle tanımlanan düzenli dillerle birebir aynıdır; bu durum, en basit dil sınıfının makine, cebirsel ve gramer görünümlerini bir araya getirmektedir.
- Chomsky Hiyerarşisi
- Düzenli, bağlamdan bağımsız, bağlama duyarlı ve özyinelemeli sayılabilir diller, her seviyesi bir gramer türü ve karşılık gelen bellek yapısına sahip bir otomat modeliyle eşleşen katı bir kapsama zinciri oluşturmaktadır.
Klinik önem
Sonlu otomatlar ve düzenli ifadeler, derleyicilerdeki sözcüksel analizi, metin aramasını ve protokol belirtimini güçlendirirken, bağlamdan bağımsız gramerler programlama dili ayrıştırmasının temelini oluşturmaktadır; sonsuz nesneler üzerindeki otomatlar, bir sistemin zamansal mantık belirtimine göre doğrulandığı model denetiminin algoritmik çekirdeğini teşkil etmektedir.
Tarihçe
Sonlu durum modelleri, 1940'larda McCulloch ve Pitts'in sinir ağlarından ortaya çıkmış ve yaklaşık 1951'de Kleene tarafından dil-kuramsal bir biçim verilmiştir. Rabin ve Scott, 1959'da deterministik olmayan otomatları tanıtırken, Chomsky'nin 1950'lerin sonlarındaki gramerleri, dil sınıflarını konuyu hala yapılandıran hiyerarşiye göre düzenlemiştir.
Öne çıkan isimler
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
İlgili konular
Temel eserler
- rabinScott1959
- sipser2013
- hopcroft2006
Sıkça sorulan sorular
- Sonlu bir otomat neden dengeli parantezleri tanıyamaz?
- Keyfi derinlikteki iç içe geçmiş yapıları tanımak, kaç tane eşleşmemiş açılış parantezi olduğunu saymayı gerektirmektedir ki bu, herhangi bir sabit durum sayısını aşabilmektedir. Sonlu bir otomatın yalnızca sınırlı belleği bulunmaktadır, bu nedenle bu sayma yeteneği, yığın otomatları ve bağlamdan bağımsız dillerle bir üst seviyede yer almaktadır.
- Biçimsel diller kuramının pratik getirisi nedir?
- Mühendislere belirli bir aracın hangi örüntüleri ifade edebileceğini göstermektedir. Düzenli ifadeler belirteçler (tokens) için yeterli olmakla birlikte, iç içe geçmiş yapılar için yeterli değildir; bu nedenle derleyiciler işi düzenli bir sözcüksel analizci (lexer) ile bağlamdan bağımsız bir ayrıştırıcı (parser) arasında bölmekte ve doğrulama araçları sonsuz kelimeler üzerindeki otomatlara dayanmaktadır.