Genelleştirilmiş Deterministik Olmayan Sonlu Otomat

Genelleştirilmiş deterministik olmayan sonlu otomat (kısaca GNSO), geçişlerinde yalnızca alfabenin sembolleri değil, düzenli ifadeler de bulunabilen deterministik olmayan bir otomattır.

Tanım

GNSO’ya, sonlu otomatı düzenli ifadeye dönüştüren algoritmada ihtiyaç duyacağız. GNSO, geçişleri düzenli ifadelerle tanımlanmış bir NSO’dur. Böyle bir GNSO örneği:

Örneğin q₂ durumundan q_f durumuna bir geçiş çıktığını ve bu geçişin a^∗ b düzenli ifadesiyle etiketlendiğini görüyoruz. GNSO için başka gereksinimler de var:

• q₀ başlangıç durumundan diğer tüm durumlara geçiş olmalıdır. Şekilde q₀ durumundan diğer tüm durumlara geçişler çıktığını görüyoruz.
• GNSO’da yalnızca bir kabul durumu vardır ve diğer tüm durumlardan bu duruma bir geçiş vardır. Şekilde de görüldüğü gibi her durumdan q_f durumuna giden bir ok var.
• Başlangıç durumu kabul durumuyla aynı olamaz. Dolayısıyla bir GNSO’nun en az iki durumu vardır.
• Başlangıç ve kabul durumu dışındaki diğer tüm durumlardan, başlangıç ve kabul durumu dışındaki tüm diğer durumlara geçiş olmalıdır. Döngüler de dâhildir (q_i durumundan q_i durumuna geçiş).

Sıradan Bir NSO’nun GNSO’ya Dönüştürülmesi

Elimizde bir NSO varsa GNSO’ya dönüştürmek kolaydır.

1. Yeni bir q_s başlangıç durumu oluştururuz ve bu durumdan eski başlangıç durumuna bir ε-geçişi çizeriz.
2. Yeni bir q_f kabul durumu oluştururuz ve eski kabul durumlarının hepsinden q_f durumuna ε-geçişleri çizeriz. Eski kabul durumlarını sıradan durumlara çeviririz.
3. Bir yerde birden fazla geçiş varsa (yani q₁ durumundan q₂ durumuna hem 0 hem de 1 sembolüyle gidebiliyorsak) bu kuralları tek bir düzenli ifadede birleştiririz ve eski sembollerin hepsini birleşim işleciyle bağlarız (yani oku 0|1 düzenli ifadesiyle etiketleriz).
4. Tanım gereği olması gereken bir geçiş eksikse onu oluştururuz ve ∅ düzenli ifadesiyle etiketleriz. Otomatın kabul ettiği dil değişmez, çünkü böyle bir geçiş hiçbir zaman gerçekleşmez.

Bu otomatı, bir otomatı düzenli ifadeye dönüştüren algoritmada kullanabiliriz.