Bir RE'den bir FA'nın oluşturulması

Normal bir İfadeden Sonlu Otomatı bulmak için Thompson Yapısını kullanabiliriz. Normal ifadeyi en küçük normal ifadelere indirgeyeceğiz ve bunları NFA'ya ve son olarak DFA'ya dönüştüreceğiz.

Bazı temel RA ifadeleri şunlardır -

Case 1 - 'a' düzenli ifadesi için aşağıdaki FA'yı oluşturabiliriz -

Case 2 - Normal bir 'ab' ifadesi için aşağıdaki FA'yı oluşturabiliriz -

Case 3 - Bir düzenli ifade (a + b) için, aşağıdaki FA'yı oluşturabiliriz -

Case 4 - Bir düzenli ifade (a + b) * için aşağıdaki FA'yı oluşturabiliriz -

Yöntem

Step 1 Verilen düzenli ifadeden Null hareketleri olan bir NFA oluşturun.

Step 2 NFA'dan Null geçişini kaldırın ve eşdeğer DFA'sına dönüştürün.

Problem

Aşağıdaki RA'yı eşdeğer DFA - 1 (0 + 1) * 0'a dönüştürün

Solution

Üç ifadeyi "1", "(0 + 1) *" ve "0" olarak birleştireceğiz.

Şimdi kaldıracağız εgeçişler. Kaldırdıktan sonraε NDFA'dan geçişler, aşağıdakileri elde ederiz -

RE - 1 (0 + 1) * 0'a karşılık gelen bir NDFA'dır. Bunu bir DFA'ya dönüştürmek istiyorsanız, Bölüm 1'de tartışılan NDFA'yı DFA'ya dönüştürme yöntemini uygulamanız yeterlidir.

Boş Hareketlerle Sonlu Otomata (NFA-ε)

Sıfır hamleli (FA-ε) bir Sonlu Otomat, sadece alfabe setinden girdi verdikten sonra değil, aynı zamanda herhangi bir giriş sembolü olmadan da geçiş yapar. Bu girişsiz geçişenull move.

Bir NFA-ε, resmi olarak aşağıdakilerden oluşan bir 5 tuple (Q, ∑, δ, q 0 , F) ile temsil edilir:

  • Q - sonlu bir durum kümesi

  • - sonlu bir dizi girdi sembolü

  • δ- bir geçiş fonksiyonu δ: Q × (∑ ∪ {ε}) → 2 Q

  • q0- bir başlangıç ​​durumu q 0 ∈ Q

  • F - Q'nun nihai durumu / durumları (F /Q).

Yukarıdaki (FA-ε) bir dize kümesini kabul eder - {0, 1, 01}

Sonlu Otomattan Boş Hareketlerin Kaldırılması

Bir NDFA'da, X köşesi ile Y köşesi arasında ϵ hareketi varsa, aşağıdaki adımları kullanarak kaldırabiliriz -

  • Y'den giden tüm kenarları bulun.
  • Kenar etiketlerini değiştirmeden X'ten başlayarak tüm bu kenarları kopyalayın.
  • X bir başlangıç ​​durumu ise, Y'yi de bir başlangıç ​​durumu yapın.
  • Y nihai bir durumsa, X'i de son durum yapın.

Problem

Aşağıdaki NFA-ε'yi Null hareketi olmadan NFA'ya dönüştürün.

Solution

Step 1 -

Burada ε geçişi q1 ve q2Öyleyse izin ver q1 dır-dir X ve qf dır-dir Y.

Burada q f'den giden kenarlar, 0 ve 1 girişleri için q f'dir .

Step 2 -

Şimdi , q f'den kenarları değiştirmeden tüm bu kenarları q 1'den kopyalayacağız ve aşağıdaki FA'yı alacağız -

Step 3 -

Burada q 1 bir başlangıç ​​durumudur, dolayısıyla q f'yi de bir başlangıç ​​durumu yaparız .

Böylece FA -

Step 4 -

Burada q f son durumdur, dolayısıyla q 1'i de son durum yaparız .

Böylece FA -