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 -
