NFA-, NFA, DFA dönüşümü
1
L = {w | w, en az bir tane 1 içerir ve son 1’i çift
sayıda 0 izler} kümesi için DFA
2
Nondeterministic Finite Automaton (NFA)
• DFA’nın daha genelleştirilmiş biçimidir.
– Herhangi bir durumda iken bu durumdan bazı geçişler
olmayabilir.
– Bir geçişten birden fazla olabilir.
• Avantaj: Esneklik
– Tasarım daha kolay hale gelmektedir.
3
NFA nasıl çaışır?
• NFA’nın başlangıç durumundan başlanarak, ilgili
katar izlenip bir kabul durumunda biterse w NFA
tarafından kabul edilir.
• NFA tarafından kabul edilen dil, bu NFA
tarafından kabul edilen karakter katarlarının
kümesidir.
4
NFA L = {w in {0,1}* | w’nin sondan ikinci
sembolü 1’dir}
5
NFA L = {w in {0,1}* | w’nin sondan ikinci
sembolü 1’dir}
110
6
NFA A = {w in {0,1}* | w’nin sondan ikinci
sembolü 1’dir}
110
7
NFA L = {w in {0,1}* | w’nin sondan ikinci
sembolü 1’dir}
110
8
NFA L = {w Є{0,1}* |w’nin sondan ikinci sembolü
1’dir}
110
9
NFA’nın biçimsel tanımı
• NFA M = (Q, , δ, s, F) Burada;
–
–
–
–
–
•
Q – Durumların sonlu kümesi
 - Giriş alfabesi
s – Başlangıç durumu
F  Q – Kabul durumları kümesi
δ bir durum geçiş fonksiyonudur ve Q X  Q’nin alt
kümesidir.
(p, u, q) δ’de ise , NFA p durumunda u okuyabilir ve q
‘ya gider.
10
NFA’nın biçimsel tanımı (devam)


δ*(q, w) bir durumlar kümesidir ve
p ε δ*(q, w) ise q’dan p’ye w etiketli bir yol vardır.


δ*(q0, 1) = ?


Cevap: {q0, q1}
δ*(q0, 11) = ?

11
Örnek:
Cevap: {q0, q1, q2}
NFA kabulü
• δ*(q0, w)  F kümesi bir boş küme değilse w
karakter katarı M makinesi tarafından tanınır.
NFA’nın tanıdığı dil:
• L(M) = {w in * | w, M tarafından tanınır}.
12
NFA ve DFA’nın karşılaştırılması
• NFA , DFA’dan daha mı güçlüdür?
– Cevap: Hayır
• Theorem:
– Her NFA makinesi için eşdeğer bir DFA vardır.
13
Eşdeğer DFA’nın bulunması
• NFA M = (Q, , δ, s, F)
• DFA M' = (Q', , , s', F') Burada:
–
–
–
–
14
Q' = 2Q
s' = {s}
F' = {P | P  F≠Φ}
({p1, p2, pm}, ) = δ*(p1, ) δ *(p2, )  ...  δ*(pm, )
Örnek:Eşdeğer DFA’nın bulunması
NFA
15
16
Boşluk geçişli NFA

Durumların boşluk kapanması: δ*(q, ).


17
gösterim: e-closure(q).
Örnek:
• Durumun boşluk kapanmasının bulunması:
– e-closure({s1, ... , sm}) = e-closure(s1)  ...  e-closure(sm)
s' = e-closure({s}) olsun ve
({p1,..., pm}, ) = e-closure(δ*(p1, ))  ...  e-closure(δ*(pm, ))
18
Örnek
19
δ*(q0,0)=(δ(q0,0) δ(q1,0) δ(q2,0))=
{q0,q2}={q0,q1,q2}
δ*(q0,1)= (δ(q0,1) δ(q1,1) δ(q2,1))= {q1}={q1,q2}
δ*(q1,0)= (δ(q1,0) δ(q2,0))= {q2}
δ*(q1,1)= (δ(q1,1) δ(q2,1))= ({q1})={q1q2}
δ*(q2,0)= (δ(q2,0))= ({q2})={q2}
δ*(q0,1)= (δ(q2,1))=Φ=null
20
21
• Teorem:
– (a) Her regüler ifade için eşdeğer bir NFA vardır.
– (b) Her DFA için eşdeğer bir regüler ifade vardır.
22
a+(ab)+ regüler ifadesinin tanımlamış olduğu dili tanıyan NFA’yı çiziniz. Bu NFA’ya eşdeğer DFA’yı çiziniz.
δ(q0,a)={q1,q2}
δ(q0,b)=Φ
δ({q1,q2},a)= Φ
δ({q1,q2},b)={q3}
δ(Φ, a)= δ(Φ,b)= Φ
δ(q3,a)={q2}
δ(q3,b)= Φ
δ(q2,a)= Φ
δ(q2,b)= {q3}
23
Aşağıda verilen boşluk geçişli NFA’ya karşılık gelen NFA yı bulunuz.
(q0)={q0, q1}
δ(q0,a)= δ({q0, q1},a)= δ(q0,a) δ(q1,a) ={q3,q4}
({q3,q4})={ q1, q3, q4, q5}
q0’dan b simgesiyle ulaşabileceğim durumları
listelemek için aşağıdaki adımlar uygulanır.
(q0)={q0, q1}
δ(q0,b)= δ({q0, q1},b)= δ(q0,b) δ(q1,b) ={q2}
({q2})={ q2}
24
Örnek
NFA M 1


L
M

{
10
}
*
1
0
q0
q1
1
FA M 2


L
M

{
10
}
*
2
q0
0 ,1
0
1
q1
1
q2
0
25
NFA’nın
tanıdığı dil

Regüler
Diller
DFA tarafından
kabul edilen Diller
Bu yüzden NFA ve DFA aynı hesaplama
gücüne sahiptir.
26
NFA
tarafından
kabul edilen
diller
NFA
tarafından
kabul edilen
diller

Regüler
Diller

Regüler
Diller
27
NFA’dan DFA’ya dönüşüm
a
NFA M
q0
a

q1
q2
b
FA
M
q0
28
NFA’dan DFA’ya
a
NFA M
q0
a

q1
q2
b
FA
M
q0
a


q
,q
1
2
29
NFA’dan DFA’ya
a
NFA M
q0
a

q1
q2
b
FA
M
a
q0


q
,q
1
2
b

30
NFA’dan DFA’ya
a
NFA M
q0
a

q1
q2
b
FA
a
M
a
q0


q
,q
1
2
b

31
NFA’dan DFA’ya
a
NFA M
q0
a

q1
q2
b
FA
a
b
M
a
q0


q
,q
1
2
b

32
NFA’dan DFA’ya
a
NFA M
q0
a

q1
q2
b
FA
a
b
M
q0
a


q
,q
1
2

a, b
b
33
NFA’dan DFA’ya
a
NFA M
q0
a

q1
b
FA
q2


L
M

L
(
M
)
a
b
M
q0
a


q
,q
1
2

a, b
b
34
NFA’dan to DFA’ya dönüşüm işlem sırası
1.
NFA’nın başlangıç durumu: q 0
FA ’nın başlangıç durumu :
q0
35
Örnek
a
NFA M
q0
a

q1
q2
b
FA M 
q0
36
NFA’dan FA’ya
q
,
q
,...,
q
}
2. FA’nın her durumu için {
i
j
m
NFA’nın rekürsif geçiş fonksiyonu
 *  q i , a ,
 * q j , a ,


}
q
,
q
,...,
q
 {
i
j
m
...


geçişleri FA’ya eklenir.




{
q
,
q
,...,
q
},
a

{
q
,
q
,.
q
}
i
j
m
i
j
m
37
Örnek
a
NFA M
a
q0
q1

q2

b
*
(
q
,
a
)

{
q
,
q
}
0
1
2
FA M 
q0
a


q
,q
1
2






q
,
a
q
,
q
0
1
2
38
NFA’dan DFA’ya
Adım 2 alfabedeki bütün geçişler (yeni
geçişler eklenemeyinceye kadar) için
tekrarlanır.
39
Örnek
a
NFA M
q0
a

q1
q2
b
FA
a
b
M
q0
a


q
,q
1
2

a, b
b
40
NFA’dan DFA’ya
3. Herhangi bir FA durumu
{
q
,
q
,...,
q
}
i
j
m
Eğer q j NFA’da bir kabul durumu ise
FA’da kabul durumu olur.
{
q
,
q
,...,
q
}
i
j
m
41
Örnek
a
NFA M
q0
a

q1
q2
q
1 F
b
FA
a
b
M
a
q0


q
,q
1
2



q
,
q

F
1
2
b

a, b
42
Bir NFA tek kabul durumlu eşdeğer bir
NFA’ya dönüştürülebilir.
43
a
a
Örnek
NFA
b
b
Tek kabul durumlu
eşdeğer NFA?
44
a
Örnek
NFA
b
a
b
Eşdeğer NFA
a
a
b
b


45
NFA
Genelleme
Eşdeğer NFA



Tek kabul
durumlu
46
Teşekkürler
47
Download

NFA FA