Sonlu Durum Makineleri ve Düzenli Diller
Sonlu durum makineleri, sınırlı sayıda dahili durum kullanarak girdiyi sembol sembol okuyan en basit hesaplama makineleridir ve tanıdıkları diller tam olarak düzenli dillerdir.
Tanım
Sonlu durum makinesi, sonlu bir durum kümesi, girdi sembolleri üzerinde bir geçiş fonksiyonu, bir başlangıç durumu ve kabul durumlarına sahip bir makinedir; bir dizgiyi okumak onu başlangıç durumundan bir kabul durumuna götürürse o dizgiyi kabul eder ve kabul edilen dizgilerin kümesi onun dilidir.
Kapsam
Bu konu, deterministik ve nondeterministik sonlu durum makinelerini, alt küme yapısı (subset construction) aracılığıyla eşdeğerliklerini, düzenli ifadeleri ve Kleene teoremini, Myhill–Nerode teoremini ve durum minimizasyonunu, düzenli dillerin kapanma özelliklerini ve belirli dillerin düzenli olmadığını kanıtlamak için kullanılan pompalama lemmasını kapsamaktadır.
Temel sorular
- Yalnızca sabit, sonlu miktarda bellek kullanılarak hangi diller tanınabilir?
- Deterministik ve nondeterministik sonlu durum makineleri neden eşit derecede güçlüdür?
- Belirli bir dilin düzenli olmadığını nasıl kanıtlayabiliriz?
- Verilen bir düzenli dili tanıyan en küçük otomat nedir?
Temel kuramlar
- Alt küme yapısı (Subset construction)
- Herhangi bir nondeterministik sonlu durum makinesi, durumları orijinal durumların kümeleri olan deterministik bir makine tarafından simüle edilebilir; bu da iki modelin tam olarak aynı dilleri tanıdığını kanıtlamaktadır.
- Kleene teoremi
- Bir dil, ancak ve ancak düzenli bir ifade ile tanımlanabiliyorsa bir sonlu durum makinesi tarafından tanınır; bu da düzenli dillerin makine ve cebirsel tanımlarının eşdeğerliğini ortaya koymaktadır.
- Myhill–Nerode teoremi
- Bir dil, ancak ve ancak dizgi ayırt edilemezliği (string indistinguishability) ilişkisi sonlu sayıda sınıfa sahip olduğunda düzenlidir ve bu sınıflar, dil için benzersiz minimal deterministik otomatı belirlemektedir.
Klinik önem
Sonlu durum makineleri, düzenli ifade eşleştirmesinin, derleyicilerdeki tarayıcıların ve sözcüksel analizörlerin, metin düzenleyicilerdeki arama-değiştirme işlevlerinin ve ağ saldırı tespit sistemlerindeki örüntü algılamanın arkasındaki temel mekanizmadır; burada sınırlı bellek tanıma, işlemeyi hızlı ve öngörülebilir kılmaktadır.
Tarihçe
McCulloch ve Pitts'in 1943 tarihli sinir ağı modelinden yola çıkarak, Kleene 1951 civarında sonlu durum makinelerinin temsil edebileceği olayları karakterize etmiştir. Rabin ve Scott ise 1959'da nondeterministik otomatları ve karar problemlerini resmileştirmişlerdir; bu çalışma daha sonra Turing Ödülü ile tanınmıştır.
Öne çıkan isimler
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Anil Nerode
İlgili konular
Temel eserler
- rabinScott1959
- sipser2013
Sıkça sorulan sorular
- Bir dilin düzenli olmadığını nasıl gösteririz?
- En yaygın araç, düzenli bir dildeki yeterince uzun her dizginin, dilde kalırken istenilen sayıda tekrarlanabilen bir alt dizgi içerdiğini belirten pompalama lemmasıdır. Bu şekilde pompalanamayan bir dizgi bulmak, dilin düzenli olmadığını kanıtlar; Myhill–Nerode teoremi ise sonsuz sayıda ayırt edilebilir önek göstererek alternatif bir argüman sunmaktadır.
- Nondeterministik otomatlar daha güçlü değilse, neden kullanılırlar?
- Genellikle çok daha küçük ve tasarlaması veya düzenli bir ifadeden türetmesi daha kolaydır. Alt küme yapısı (subset construction), gerektiğinde onları deterministik forma dönüştürebilir, ancak bu durum sayısında olası bir üstel maliyetle gerçekleşebilir; bu nedenle nondeterminizm, tanıma gücünde bir artıştan ziyade uygun bir spesifikasyon aracıdır.