Bu bölümde NFA'yı eşdeğer DFA'ya dönüştürme yöntemini tartışacağız. NFA'da mevcut duruma belirli bir giriş verildiğinde makine birden fazla duruma gider. Belirli bir giriş sembolü üzerinde sıfır, bir veya birden fazla hamle olabilir. DFA'da ise mevcut duruma belirli bir giriş verildiğinde makine yalnızca bir duruma gider. DFA'nın belirli bir giriş sembolü üzerinde yalnızca bir hareketi vardır.
M = (Q, ∑, δ, q0, F), L(M) dilini kabul eden bir NFA olsun. L(M) = L(M') olacak şekilde M' = (Q', ∑', q0', δ', F') ile gösterilen eşdeğer DFA bulunmalıdır.
NFA'yı DFA'ya dönüştürme adımları:
Aşama 1: Başlangıçta Q' = ϕ
Adım 2: Q'ya NFA'nın q0'ını ekleyin. Daha sonra bu başlangıç durumundaki geçişleri bulun.
Aşama 3: Q'da her giriş sembolü için olası durum kümesini bulun. Eğer bu durumlar kümesi Q'da değilse, onu Q'ya ekleyin.
geçersiz 0
Adım 4: DFA'da son durum, F'yi içeren tüm durumlar olacaktır (NFA'nın son durumları)
Örnek 1:
Verilen NFA'yı DFA'ya dönüştürün.
monitör boyutumu nasıl öğrenirim
Çözüm: Verilen geçiş diyagramı için öncelikle geçiş tablosunu oluşturacağız.
| Durum | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1,q2} | q1 |
| *q2 | q2 | {q1,q2} |
Şimdi q0 durumu için δ' geçişini elde edeceğiz.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
q1 durumu için δ' geçişi şu şekilde elde edilir:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
q2 durumu için δ' geçişi şu şekilde elde edilir:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Şimdi [q1, q2] üzerinde δ' geçişini elde edeceğiz.
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] [q1, q2] durumu aynı zamanda son durumdur çünkü bir q2 son durumu içerir. Oluşturulan DFA'nın geçiş tablosu şöyle olacaktır:
| Durum | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Geçiş diyagramı şöyle olacaktır:
q2 durumu ortadan kaldırılabilir çünkü q2 ulaşılamaz bir durumdur.
karakter tostring java
Örnek 2:
Verilen NFA'yı DFA'ya dönüştürün.
Çözüm: Verilen geçiş diyagramı için öncelikle geçiş tablosunu oluşturacağız.
| Durum | 0 | 1 |
|---|---|---|
| →q0 | {q0,q1} | {q1} |
| *q1 | ϕ | {q0,q1} |
Şimdi q0 durumu için δ' geçişini elde edeceğiz.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] q1 durumu için δ' geçişi şu şekilde elde edilir:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Şimdi [q0, q1] üzerinde δ' geçişini elde edeceğiz.
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Benzer şekilde,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Verilen NFA'da olduğu gibi, q1 bir son durumdur, o zaman DFA'da q1'in var olduğu her yerde bu durum bir son durum haline gelir. Dolayısıyla DFA'da son durumlar [q1] ve [q0, q1]'dir. Bu nedenle son durumlar kümesi F = {[q1], [q0, q1]}.
log4j
Oluşturulan DFA'nın geçiş tablosu şöyle olacaktır:
| Durum | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Geçiş diyagramı şöyle olacaktır:
Hatta DFA'nın durumlarının adını bile değiştirebiliyoruz.
Sanmak
A = [q0] B = [q1] C = [q0, q1]
Bu yeni adlarla DFA şu şekilde olacaktır:
