Biçimsel Diller Ve Otomata Teorisi -2

İKİNCİ BÖLÜM

FINITE AUTOMATA -SONLU OTOMATA

Sonlu durum makineleri bir çizim şeklidir. Bu çizim şeklinde çeşitli durumlar ve bu durumlar arası geçiş şekilleri gösterilir.

Sonlu bir otomat üç şeyden oluşan bir koleksiyondur:
1. Biri başlangıç durumu olarak adlandırılan, bazıları başlangıç durumu olarak adlandırılan ve bazıları (belki de hiçbiri) son durumlar olarak adlandırılan sonlu durum kümesi.
2. Her seferinde bir harf okunacak olan dizeler olan olası giriş harflerinin ∑ alfabesi.
3. Her durum için ve giriş alfabesinin her harfine bir sonraki aşamaya geçecek şekilde söylenen sonlu geçişler kümesi.

Sonlu otomatı FA şeklinde kısaltabiliriz.

Bir örnekle açıklayalım;

Geçiş kuralları listesi çok uzayabilir. Bunları tablo biçiminde özetlemek çok daha kolaydır. Tablonun her satırı FA’daki durumlardan birinin adıdır ve tablonun her sütunu giriş alfabesinin bir harfidir. Tablonun içindeki girdiler, FA’nın geçiş durumlarına geçtiği yeni durumlardır.

içerisinde en az bir b içeren kelimeler

Açıkladığımız FA için geçiş tablosu:

Transition Table (Geçiş Tablosu)

TRANSITION DIAGRAM

Tek durumlu otomatalarda başlangıç ve bitiş aynıdır.

Tek durumlu Otomata

(a+b)*={ λ,a,b,aa,…}

Aşağıdaki diyagram bir otomatadır ama kabul ettiği hiçbir girdi yoktur.

Aşağıdaki diyagram otomata değildir başlangıçtan sonlu duruma gidecek bir yol yok.

NOT:

Otomata olabilmesi için alfabedeki her bir girdinin nereye gideceğini otomata da göstermek gerekir.

a ile başlayan kelimeleri kabul eden otomata

{a,aa,ab,aaa,aab,aba,abb,aaaa,…}

Aşağıdaki diyagram otomata değildir,olması için deterministic olmalıdır.

Birkaç diyagram örneklerine bakalım:

İlk harfi ne olursa olsun 3. harfi ‘b’ olursa kabul eden diyagram

Kuralı; (a+b)(a+b)b(a+b)*

Birtek {bba} kabul eden program

Kuralı; a*(a*ba*ba*ba*)*(a + a*ba*ba*ba*)

Kuralı; (a + ba*ba*b)+

{λ} kabul eder.

Kuralı; En az içerisinde bir “aa” olan diyagram

TRANSITION GRAPHS(TGs)

TG olarak kısaltılmış bir geçiş grafiği üç şeyin toplamıdır:
1. En az bir tanesi başlangıç durumu (-) ve bazıları (belki de hiçbiri) son durum (+) olarak belirlenmiş sonlu durum kümesi.
2. Giriş dizelerinin oluşturulduğu olası giriş harflerinin bir alfabesi ∑.
3. Girdi harflerinin belirtilen alt dizelerini (muhtemelen boş null dizesi A) okumaya dayalı olarak bir durumdan diğerine nasıl gidileceğini gösteren sonlu geçişler kümesi.

Kuralı ;{baa} kabul eder

Kuralı; (abb)(λ)(aa)(b)

Kuralı; Bu da transition graph sadece {λ} kabul eder.

Kuralı; b ile bitenler de transition graph

Kuralı; en az 3 b ile biten (aa+b)*bbb

Kuralı; a’ların ve b’lerin sayısı çift

İkinci Bölümü bu bilgilerle sonlandırıyorum. Çok yakında yeni bölümlerle serimize devam edeceğim. Umarım beğenirsiniz. Bir sonraki yazımda görüşmek üzere. 👽

Beni Linkedin ve Twitter hesaplarımdan da takip edebilirsiniz!🐞

Kaynaklar

1-INTRODUCTION TO COMPUTER THEORY -Daniel I. A. Cohen Hunter College City University of New York