Otomata Teorisi V (Automata Theory V)

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. L1^R Reverse (Ters Çevir)

5. L1 Complement (Tümleyen)

6. L1 ∩ L2 Intersection (Kesişim)

Sonlu Durum Dönüşümü (Final State Transformation)
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= { aⁿb } L2= { ba }

L1 U L2 = { aⁿb } 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 = { aⁿb } { ba } = { aⁿbba }

Level I

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*

NFA Yıldız Özelliği

Egzersiz

L1* = { aⁿb }*

Level I

Ters Çevirme İşlemi (Reverse Operation)
L1^R 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.

L1^R

L( M1 ) = L1 L( M1' ) = L1^R

Egzersiz

L1 = { aⁿb } L1R = { baⁿ }

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 = { aⁿb } L1' = { a, b }* - { aⁿb }

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.