L1 ve L2 dil tanımları olmak üzere:
1. L1 U L2
Union (Birleşim)
2. L1L2 Concatenation (Birleştirme)
3. L1* Star (Yıldız)
4. L1R Reverse (Ters Çevir)
5. L1 Complement (Tümleyen)
6. L1 ∩ L2 Intersection (Kesişim)
Oluşturulan NFA'da birden fazla final state bulunursa, NFA'da bulunan final state davranışı değiştirilir, final state sayısı kadar λ (lambda) ile oluşturulan final state geçiş sağlanır.
L( M1 ) = L1
Birleşim İşlemi (Union Operation)
L( M1 ) = L1 L( M2 ) = L2
L1 U L2 için oluşturulacak NFA'da bir initial state eklenir ve L1, L2 NFA'larına λ (lambda) geçişleri oluşturulur.
L1 U L2
NFA Birleşim Özelliği |
Egzersiz
L1= { anb } L2= { ba }
L1 U L2 = { anb } U { ba } |
Level I |
Birleştirme İşlemi (Concatenation Operation)
L( M1 ) = L1 L( M2 ) = L2
L1L2 için oluşturulacak NFA'da L1, L2 NFA'ları birleştirilir ve NFA'lardan başta olanın diğer NFA ile geçiş sağlaması için final state davranışı değiştirilir.
L1L2
NFA Birleştirme Özelliği |
Egzersiz
L1L2 = { anb } { ba } = { anbba }
Yıldız
İşlemi (Star Operation)
L1* için oluşturulacak NFA'da bir initial state ve final state eklenir ve L1 NFA'nın final state davranışı değiştirilir. İnitial state, final state ulaşması için 4 λ (lambda) geçişi oluşturulur.
L1* için oluşturulacak NFA'da bir initial state ve final state eklenir ve L1 NFA'nın final state davranışı değiştirilir. İnitial state, final state ulaşması için 4 λ (lambda) geçişi oluşturulur.
L1*
NFA Yıldız Özelliği |
Egzersiz
L1* = { anb }*
Level I |
Ters
Çevirme İşlemi (Reverse Operation)
L1R için oluşturulacak NFA'da tüm geçişlerin yönü ters çevrilir ve L1 NFA'sında final state'ler diğer durumlara, diğer durumlar ise final state'lere dönüştürülür.
L1R için oluşturulacak NFA'da tüm geçişlerin yönü ters çevrilir ve L1 NFA'sında final state'ler diğer durumlara, diğer durumlar ise final state'lere dönüştürülür.
L1R
L( M1 ) = L1 L( M1' ) = L1R
Egzersiz
L1 = { anb } L1R = { ban }
Tümleyen İşlemi (Complement Operation)
L1' oluşturulacak NFA'da geçişlerin yönleri değiştirilmez ve L1 NFA'sında final state'ler, diğer durumlara, diğer durumlar ise final state'lere dönüştürülür.
L( M1 ) = L1 L( M1' ) = L1'
Egzersiz
L1 = { anb } L1' = { a, b }*
- { anb }
De Morgan Kanunu (De Morgan’s Law)
L1 ∩ L2 = ( L1' U L2' )'
Kesişim İşlemi (Intersection Operation)
L( M1 ) = L1 L( M2 ) = L2
L1 ∩ L2 oluşturulacak NFA'da tüm durumların birbirleriyle kartezyen çarpımı sonucu oluşturulan yeni durumlar arası geçişler L1 ve L2'deki geçişlere göre oluşturulur. L1, L2 final state'lerinin kartezyen çarpımı kadar L1 ∩ L2'de final state oluşturulur.
Level I |
Bir sonraki yazımda görüşmek üzere...