Otomata Teorisi V (Automata Theory V)

watch_later 3/30/2016
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)


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= { 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 }
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* = { 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

                   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.


 Egzersiz

        L1 = { anb }                                                                                                          L2 = { abm }                       
                                                    



                       
                            



 L = { anb } ∩ { abn } ={ ab }

Level I








Bir sonraki yazımda görüşmek üzere...



sentiment_satisfied Emoticon