Otomata Teorisi IV (Automata Theory IV)

Düzenli İfadeler ve NFA (Regular Expressions and NFA)

Deterministik Olmayan Sonlu Otomata (Non-Deterministic Finite Automata)

DFA'daki, her bir giriş sembolü için, makinenin bir hareket durumunun ifadesidir. Dolayısıyla sonlu sayıda duruma  sahip olduğundan sonlu durum makinesi de denir. 

NFA  6 başlığın ile temsil edilebilir (Q, Σ, δ, q0, F, δ*):

1. Q durumların kümesidir.

2. Σ alfabesi denilen sembollerin bir kümesidir.

3. δ Σ → Q × Q: karakterlerle geçiş fonksiyonudur.

4. q0 (q0 ∈ Q) başlangıç durumunu ifade eder.

5. F Q (F ⊆ Q) sonlu durumların kümesidir.

6. δ* = { q, word } =q' string ile geçiş fonksiyonudur.

Egzersiz

L(( a + bc )*) dilinin oluşturduğu düzenli ifade: 

{ a, bc }* = { λ, a, bc, aa, abc, bca, … }

Rekürsif Tanım (Recursive Definition)

Düzenli ifadelerin ilkel yapıları (primitives)

1. Ø (Boş küme belirtir.)

2. λ (Boş string belirtir.)

3. a (Dili tanımlayan herhangi bir karakter belirtir.)

İlkel Yapıların Dil Özellikleri (Language Properties of Primitives)

1. L( Ø ) = Ø

2. L( λ ) = { λ }

3. L( a ) = { a }

r1 ve r2 düzenli ifade tanımları olmak üzere:

1. L( r1+ r2 ) = L( r1 ) U L( r2 )

2. L( r1r2 ) = L( r1 )L( r2 )

3. L( r1* ) = ( L( r1 ) )*

4. L( ( r1 ) ) = L( r1 )

Egzersiz

L( ( a + ba* ) ) = L( ( a + b ) ) L( a* )

                         = L( a + b ) L( a* )

                         = L( ( a ) U L( b ) ) L( ( a ) )*

                         = ( { a } + { b } ) (( { a } )*

                         = { a, b } { λ, a, aa, aaa, … }

                         = { a, aa, aaa, …, b, ba, baa, … }

Egzersiz

r = ( aa )* ( bb )*b düzenli ifadesi tanımlanmış olsun. Buna göre bu düzenli ifadenin dili:

L( r ) = { a²ⁿb^2mb:   n, m ≥ 0 }

Egzersiz

r = ( 0 + 1 )* 00( 0 + 1 )* düzenli ifadesi tanımlanmış olsun. Buna göre bu düzenli ifadenin dili:

L( r ) = { tüm stringleri 00 içeren dil tanımı }

Egzersiz

r = ( 1 + 01 )* ( 0 + λ ) düzenli ifadesi tanımlanmış olsun. Buna göre bu düzenli ifadenin dili:

L( r ) = { tüm stringleri 00 içermeyen dil tanımı }

Eşdeğer Düzenli İfadeler (Equivalent Regular Expressions)

r1 ve r2 düzenli ifade tanımları olmak üzere:

L( r1 ) ve L ( r2 ) eşdeğer ise,

L( r ) = { tüm stringleri 00 içermeyen dil tanımı }

r1 = ( 1 + 01 )* ( 0 + λ )

r2 = ( 1* 011* )* (( 0 + λ ) + 1*( 0 + λ ))

L( r1 ) = L( r2 ) = L olduğu için r1 ve r2 düzenli ifadeleri eşdeğerdir.

İlkel Yapılar ve NFA (Primitives and NFA)

1. L( Ø ) = Ø 

                         

2. L( λ ) = { λ }

                         

3. L( a ) = { a }

                         

L( r1 + r2 ) = L( r1 ) U L( r2 ) Kapalılık Özellliği

r1 ve r2  düzenli ifadelerinin NFA'ları oluşturulsun. L( r1 + r2 ) = L( r1 ) U L( r2 ) işlemi uygulandığında oluşacak otomata NFA davranışı gösterecektir.

             L( r1 ) = L( M1 )                                                                                             L( r2 ) = L( M2 )

                                                         

 L( r1 + r2 ) = L( r )

Birleşim Kapalılık Özellliği Sonlu Durum Makinesi

NFA ve Düzenli İfadeler Dönüşümü (NFA and Regular Expressions Convert)

Aşağıdaki ifadelerle bir sonlu olmayan durum makinesi ifade edilmektedir.

Q = { q0, qf } 

Σ = { r₁, r₂, r₃, r₄ }

Başlangıç Durumu (İnitial State) = q0

F = { qf }
δ = { q0, r₂ } = qf 
δ* = { q0, r₂r₃ } = q0

Level I

Level II

r = r₁* r₂ ( r₄+ r₃r₁* r₂ )*

L( r ) = L( M ) = L

Egzersiz

Aşağıdaki ifadelerle bir sonlu olmayan durum makinesi ifade edilmektedir.
Q = { q0, q1, q2 } 

Σ = { a, b }

Başlangıç Durumu (İnitial State) = q0

F = { q2 }
δ = { q0, b } = q1
δ* = { q0, ba } = q2

Level I

Level II

Level III

r = ( bb* a )* bb* ( a + b )b*

L( r ) = L( M ) = L 

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