Düzenli Dilin Tümleyeni

L düzenli bir dil olsun. L dilinin tümleyeninin de düzenli bir dil olduğunu ispatlayacağız.

Tümleyen Nedir?

L dilinin tümleyeni, L dilinde olmayan tüm sözcüklerdir. Tümleyeni L' ile gösteririz. Yani Σ alfabesi için şu geçerlidir:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Örneğin en az bir tane 1 sembolü içeren sözcüklerden oluşan dilin tümleyeni, hiç 1 sembolü içermeyen sözcüklerden oluşan dil olur.

Yöntem

Yöntem çok basittir. L düzenli bir dil olsun ve onu kabul eden deterministik tam otomat A = ⟨Q, Σ, δ, q₀, F⟩ verilsin (her sonlu otomat böyle bir otomata dönüştürülebilir). L' dilini kabul eden A' otomatını, kabul durumlarıyla kabul etmeyen durumları yer değiştirerek kurarız: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Hepsi bu kadar.

Örnek

Şu otomatı ele alalım:

Dilin tümleyenini kabul eden otomat şöyle görünürdü: