Ulaşılamayan Durumlar

Sonlu otomatın bazı durumlarına ulaşmak mümkün olmayabilir. Bu tür durumlara ulaşılamayan durumlar diyoruz. Bunları genellikle çıkarmak isteriz, çünkü otomatı gereksiz yere karmaşıklaştırırlar.

Ulaşılamayan Durumlara Örnek

Şu otomata bakalım:

Ne yaparsak yapalım q₃ durumuna hiçbir zaman ulaşamayız, çünkü ona giden hiçbir geçiş yoktur. Bu yüzden q₃ durumunun ulaşılamaz olduğunu söyleriz. Bir soru: ona başka bir durumdan giden bir geçiş olsaydı, q₃ ulaşılabilir olur muydu? q₀, q₁, q₂, q₅ durumlarından birinden bir ok çizseydik olurdu. Peki yeni bir düğüm ekleyip geçişi o düğümden çizseydik…

…o zaman elbette hem q₃ hem q₄ durumları ulaşılamaz olurdu.

Ulaşılamayan Durumun Tanımı

Önce ulaşılabilir durumu tanımlayalım. A = ⟨Q, Σ, δ, q₀, F⟩ sonlu otomat olsun. q ∈ Q durumunun ulaşılabilir olduğunu, şu koşulu sağlayan bir w ∈ Σ^∗ sözcüğü varsa söyleriz:

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q,\epsilon ⟩.$$

q ∈ Q durumu ulaşılabilir değilse ulaşılamazdır.

Ulaşılamayan Durumlar Nasıl Çıkarılır

Otomatın zaten ulaşılamayan durumları varsa onları çıkarmak yerinde olur. Bunun için ulaşılamayan durumları olmayan, eşdeğer bir A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ otomatı kurarız.

Ulaşılabilir durumlar kümesini adım adım kuracağız. S₀ = {q₀} kümesiyle başlarız, çünkü başlangıç durumu kesinlikle ulaşılabilirdir. Sonraki kümeyi şöyle kurarız:

$$S_i=\{r|\delta (q,a)=r\text{ bazı }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Sade bir dille, S₀ kümesi her zaman verilmiştir. S₁ kümesini şöyle kurarız: S₀ kümesindeki tüm durumları alırız ve Σ’daki tüm simgeler için geçişlerin nereye gittiğine bakarız. Bu durumların birleşimini S₀ durumlar kümesiyle alırız. S₂ ve sonraki kümeleri de aynı yöntemle buluruz. Açıkça S_{i − 1} ⊆ S_i olacaktır.

Ulaşılabilir durumlar kümesini şöyle elde edebiliriz:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Sonsuz sayıda S_i kümesinin birleşimini almaya çalışmamız tuhaf görünebilir, ama otomatın yalnızca sonlu sayıda durumu vardır. Bu, bir noktadan sonra S_j, S_{j + 1} ve sonraki tüm kümelerin aynı olacağı anlamına gelir. Bu yüzden sonsuz sayıda kümenin birleşiminden de sonlu bir durumlar kümesi elde edebiliriz.

Şu otomata dönelim

ve ulaşılabilir durumlar kümesini bulmaya çalışalım. Temel eşitliği yazarak başlarız

$$S_0=\left\{q_0\right\}$$

Şimdi S₁ kümesini hesaplayalım. q₀ durumundan çıkan tüm geçişleri bulmalı ve hedef durumlarını S₀ kümesine eklemeliyiz. q₀ → ^a q₁ ve q₀ → ^bq₂ olduğundan S₁ kümesi ek olarak q₁ ve q₂ durumlarını içerecektir:

$$S_1=\{q_0,q_1,q_2\}$$

Sonra S₂ kümesini kuralım. q₀, q₁, q₂ durumlarından nerelere gidebileceğimize bakarız. Tek yeni durum q₅’tir, ona q₁ durumundan gidebiliriz:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Sonra S₃ kümesini kuralım. q₀, q₁, q₂, q₅ durumlarından yeni bir duruma gidebilir miyiz? Gidemeyiz, bu yüzden S₃ kümesi S₂ ile aynı elemanları içerecektir:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

S₂ = S₃ olduğundan S₃ = S₄ = S₅ = … olur. Tüm S_i kümelerinin birleşimini alırsak S₂ kümesini elde ederiz, çünkü hiçbir sonraki kümeye başka eleman eklenmez.

Otomatın ulaşılabilir durumlar kümesi böylece {q₀, q₁, q₂, q₅} olur. Ulaşılamayan durumları basit bir küme farkıyla elde ederiz:

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Otomatımızın ulaşılamayan durumlar kümesi {q₃, q₄} olur. A otomatından tüm ulaşılamayan durumları ve ulaşılamayan bir durum içeren tüm geçişleri çıkarırız. Yani A = ⟨Q, Σ, δ, q₀, F⟩ otomatına eşdeğer, ulaşılamayan durumları olmayan A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ otomatını şöyle tanımlarız:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$