Biçimsel Diller ve Otomatalar

29/11/2019

0 841 2 dakika okuma süresi

Bu yazımızda Formal languages and abstract machines yani biçimsel diller ve otomatalar dersinin girişini yapacağız.

Öncelikle bu derste makinelerin işleyişini öğreneceğiz. Makineleri de insanlar gibi kabul edersek, anlaşmaları için bir dile ihtiyacımız var. Dili de harfler oluşturur.

Σ = {0,1} ya da Σ = {a,b} olarak gösterebiliriz. Alfabeyi genişletebiliriz.

Σ = {a,b} inceleyelim. Bu alfabeden a,b,ab,ba,aba,abb,abab,baba gibi çeşitli kelimeler çıkartabiliriz. Ancak her iletişim gibi bu iletişim de bazen kopabilir. İşte o zaman makine susma hakkını kullanmak ister. Bu susma olayı aslında hiçbir şey söylememektir. Makine bu sonuçta Antik Yunanca falan bilir ve hiçlik için de lamda(λ) harfini kullanır. Tam anlamıyla boşluktur bu durum ama yine de derin anlamlar taşır.

Boş String: ε ve λ ile gösterilir. String uzunluğu 0’dır |λ|=0

wλ = λw = w

λ etkisiz eleman olduğu için 3 eşitlikte doğrudur.

Substring: Stringimizin içinde herhangibir parça demektir.

ababaaababa — -> ab bizim substringimizdir.

String Uzunluğu (|w|): String uzunluğu “|w|” şeklinde ifade edilir ( w ifadesi semboliktir)

|abcd|=4

|w|=4

|wu|=|w|+|u|

|aba| kelimesinin uzunluğu 3’tür.

|aba| = 3 olarak gösterebiliriz.

Bazı zamanlarda da tekrarlamalar yapmamız gerekebilir. Tam bu noktada yavaş yavaş olayın içerisine giren matematik kontrolü ele almaya başlar. Üslü sayılar makinemiz için kolaylık sağlayıp sürekli tekrar yapmasının önüne geçer.

– Bu da böyle olsun?
– Olsun²
– Beğendin mi?
– Güzel²

Dilimizi biraz şekillendirdikten sonra bu dilimiz ile artık yavaş yavaş iletişim kurabiliriz. Ancak bu sefer bize kelimeler gerekiyor. Dil dediğimiz kavramı da makinemize anlatabilmek için “L” dememiz yeterli.

L = {“baba”,”baaa”, “baa”}

-baba baa baaa?
-baa
-baaa

Reverse İşlemi : w stringini reverse edecek olursak tek yapmamız gereken tersten yazmak olacaktır (dcba)

Biraz daha ileri gidebiliriz ve artık alfabemize çeşitli işlemler uygulayıp sınırsız kelimeden oluşan bir dil yaratılabilir. “*” ve “⁺” sembolleri aslında tam olarak bu işe yarar. Bu sembolleri kullanarak elimizdeki alfabe ile sınırsız sayıda kelime oluşturabiliriz ama bir fark var : Bu sembollerden bir tanesi susmayı biliyor. ‘*’ işaretinin adı Kleene Star. Bu işaret olduğu zaman harfler dilediği kadar tekrar edebiliyor.

Üstel olduğu durumlar:

w^n =wwwwww….

(abab)²= abababab( üsteli kadar yan yana yazıyoruz)

w⁰= λ ( 0 kere tekrarlancağı için boş küme olan λ ya eşittir.)

* (Star) Operasyonu :

Biz bir alfebenin önüne starı ( yıldızı (*)) koyduğumuz zaman o alfade istediği kadar istediği kombinasyonu yapabilir ya da yapmayabilir.

Σ* Σ={a,b} , Σ*={λ,a,b,ab,ba,aa,bb,aaa,……..}

Σ = {a,b}
Σ* = {λ, a, b, aa, ab, bb, ba, aaa, aab, abb, bbb , bba, baa, bab, aba…}
Σ⁺ = {a, b, aa, ab, bb, ba, aaa, aab, abb, bbb , bba, baa, bab, aba…}

Bu şekilde bir kelime kümesi oluşturmak mümkün. Makineler bilindiği üzere kümeleri çok severler. Yeter ki onlara kümelerden elemanlardan falan bahsedin, sizinle çok iyi anlaşacaktırlar. Buradan da görüldüğü üzere tüm küme işlemleri artık geçerlidir.

{“seni”, “çok”} ∪ {“seviyorum”} = {“seni”, “çok”, “seviyorum”}
{“beni”, “çok”} ∩ {“beni”, “seviyorum”} = {“beni”}

Diyelim ki her şeyi güzelce oluşturduk, alfabemiz tamam, kelimelerimiz tamam. Ama sırf keyfi olarak bir de tersini almak istersek. “‾” yazmamız yeterli olacaktır, makine diyecektir ki : “aaa üstünde çizgi var, hemen ters yapayım”.

L = {“baba”, “ana”, “aile”}
‾L = {“abab”, “ana”, “elia”}