Biçimsel Diller ve Soyut Makineler
Hafta 5
1
Regüler Dillerin kapalılık özelliği

Regüler diller aşağıdaki işlemlerde kapalılık özelliğine
sahiptir.

Birleşim


Kesişim


2
Gösterim: 
Gösterim: 
Eğer L1 ve L2 regüler ise L1  L2 ve L1  L2
regulerdir.
Örnek
 = {a,b}.
L1 = { w Є{a,b}* | w çift sayıda a içerir.}
–
L1 regular midir?
L2 = L2 = { w Є{a,b}* | w tek sayıda b içerir.}
–
L2 regular midir?
L1  L2 = ?
–
–
3
L1  L2 = {w Є {a,b}* | w, çift sayıda a VEYA tek sayıda b içerir.} L1  L2 = ?
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE tek sayıda b içerir.}
L1 = { w Є{a,b}* | w çift sayıda a içerir.}
kümesi için DFA
4
L2 = { w Є{a,b}* | w tek sayıda b içerir.}
kümesi için DFA
5
 ve  için DFA gerçekleştirme
M1 = (Q1, , 1, s1, F1) ve
M2 = (Q2, , 2, s2, F2) makineleri verilmiş olsun.
Yeni bir makine  ve  için tasarlamak istiyoruz.
M = (Q, , , s, F) bu makine olsun. Burada
Q = Q1 X Q2
s = (s1, s2)
((q1, q2), ) = (1(q1, ), 2(q2, ))
Birleşim kümesi için, F = ?
•
–
Cevap: (Q1 X F2) U (F1 X Q2)
Kesişim Kümesiiçin, F = ?
•
–
6
Cevap: F1 X F2
L1  L2 = {w Є {a,b}* | w, çift sayıda a
VEYA tek sayıda b içerir.}kümesi için DFA
7
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE
tek sayıda b içerir.}kümesi için DFA
8
L1  L2 = {w Є {a,b}* | w, çift sayıda a
VEYA tek sayıda b içerir.}kümesi için DFA
aba
9
L1  L2 = {w Є {a,b}* | w, çift sayıda a VEYA
tek sayıda b içerir.}kümesi için DFA
aba
10
L1  L2 = {w Є {a,b}* | w, çift sayıda a VEYA
tek sayıda b içerir.}kümesi için DFA
aba
11
L1  L2 = {w Є {a,b}* | w, çift sayıda a
VEYA tek sayıda b içerir.}kümesi için DFA
aba
12
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE tek
sayıda b içerir.}kümesi için DFA
aba
13
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE tek
sayıda b içerir.}kümesi için DFA
aba
14
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE tek
sayıda b içerir.}kümesi için DFA
aba
15
L1  L2 = {w Є {a,b}* | w, çift sayıda a VE tek
sayıda b içerir.}kümesi için DFA
aba
16
Örnek: Birleşim ve kesişim kümesinin
DFA’sının bulunması
L1 ve L2 dilleri aşağıdaki gibi
tanımlanmaktadır.
L1={xЄ(0,1)*|x katarı 00 alt katarı içermez}
L2={ xЄ(0,1)*|x katarı 01 ile biter}
L1L2 ve L1L2 dillerini tanıtan DFA’yı
çiziniz
17
L1={xЄ(0,1)*|x katarı 00 alt katarı
içermez}
L2={ xЄ(0,1)*|x katarı 01 ile biter}
18
δ(AP,0)= (δ1(A,0), δ2(P,0))=BQ
δ(AP,1)= (δ1(A,1), δ2(P,1))=AP
δ(BQ,0)= (δ1(B,0), δ2(Q,0))=CQ
δ(BQ,1)= (δ1(B,1), δ2(Q,1))=AR
……
19
L1L2 F={AP,AR,BQ,CR}
20
Download

L 1 L 2