Derleyici Tasarımı - Sonlu Otomata
Sonlu otomata, girdi olarak bir sembol dizisini alan ve durumunu buna göre değiştiren bir durum makinesidir. Sonlu otomata, düzenli ifadeler için bir tanıyıcıdır. Bir düzenli ifade dizesi sonlu otomataya beslendiğinde, her değişmez değer için durumunu değiştirir. Girdi dizisi başarılı bir şekilde işlenirse ve otomata son durumuna ulaşırsa, kabul edilir, yani yeni beslenen dizenin eldeki dilin geçerli bir belirteci olduğu söylenir.
Sonlu otomatların matematiksel modeli şunlardan oluşur:
- Sonlu durum kümesi (Q)
- Sonlu giriş sembolleri kümesi (Σ)
- Bir Başlangıç durumu (q0)
- Son durumlar kümesi (qf)
- Geçiş işlevi (δ)
Geçiş fonksiyonu (δ), sonlu durum kümesini (Q) sonlu bir girdi sembolleri kümesine (Σ), Q × Σ ➔ Q
Sonlu Otomata İnşaatı
L (r) bazı sonlu otomatlar (FA) tarafından tanınan normal bir dil olsun.
States: FA durumları dairelerle temsil edilir. Devlet isimleri dairelerin içine yazılır.
Start state: Otomatanın başladığı durum, başlangıç durumu olarak bilinir. Başlangıç durumunun kendisine dönük bir ok vardır.
Intermediate states: Tüm ara durumlar en az iki ok içerir; biri onlara işaret ediyor, diğeri ise onları gösteriyor.
Final state: Girdi dizesi başarıyla ayrıştırılırsa, otomatanın bu durumda olması beklenir. Son durum çift dairelerle temsil edilir. Kendisine işaret eden tek sayıda ok ve ondan dışarı doğru işaret eden çift sayıda ok olabilir. Tek okların sayısı çiftten bir büyüktür, yaniodd = even+1.
Transition: Bir durumdan diğerine geçiş, girişte istenen bir sembol bulunduğunda gerçekleşir. Geçişin ardından, otomata bir sonraki duruma geçebilir veya aynı durumda kalabilir. Bir durumdan diğerine hareket, okların hedef durumuna işaret ettiği yönlendirilmiş bir ok olarak gösterilir. Otomata aynı durumda kalırsa, bir durumdan kendisine işaret eden bir ok çizilir.
Example: FA'nın 1. basamakla biten herhangi bir üç basamaklı ikili değeri kabul ettiğini varsayıyoruz. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}
