Bir otomatın düzenli ifadesini (regular expression) yazınız?

Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız?

DFA

Çözüm:

DFA-RE

Arden Teoremi ile çözmeye çalışalım: Not: Henüz çözemedim
q1=q2a+q3b+null
q2=q1a+q2b+q3a
q3=q1b
oluşturulur.

q2=q1a+q2b+q3a
q2=q1a+q2b+(q1b)a
q2=q1(a+ba)+q2b
q2=q1(a+ba)+b*

q1=q2a+q3b+null
q1=(q1(a+ba)+b*)a+(q1b)b+null
q1=q1((a+ba)+b*))a+bb)+null
q1=q1((a+ba)+b*))a+bb)+null
q1=null((a+ba)+b*))a+bb)*
q1=((a+ba)+b*))a+bb)*

Etiketler: ,

9 Yorum

  1. b biten bir string tanır.
    [a/ba*]?b*

  2. Duzenli dilin duzenli ifadesini yazmak icin o dili taniyan DfA once GNFA -ya donusturulmeli.GNFA-ya donusturmek icin DfA-nin baslangic durumuna epsilon ile yeni baslangic,kabul durumlari ise epsilon ile yeni baslangic durumuna donusturulur.Daha sonra GNFA yalnizca kabul ve baslangic durumlarindan olusana kadar durumlar azaltiliyor.Ornekde ki DFA -dan 5 durumlu GNFA ortaya cikiyor.durumlar bir-bur cikariltildigi zaman gecislerin etiketlenmesi cikarilan duruma gore yapiliyor.

  3. Yalnis oldu NFA

  4. Sayın Kiambe Kevin, çözüm kitaptan alınmış 🙂 Kendin çözüm üretme, onu anlamaya çalış 😉

Yorum Yapın