Düzenli Dillerin Kesişimi

İki düzenli dil L₁, L₂ olsun. Bunların kesişimi L = L₁ ∩ L₂ kümesinin de düzenli bir dil olduğunu ispatlayacağız.

İspatın Fikri

İki düzenli dilimiz L₁ ve L₂ var ve kesişimleri L₁ ∩ L₂’nin yine düzenli bir dil olduğunu ispatlamak istiyoruz. L₁ ve L₂ düzenli diller olduğu için L₁ ve L₂ dillerini kabul eden sonlu otomatlar A₁ ve A₂ vardır, yani L(A₁) = L₁ ve L(A₂) = L₂ olur. Biz de L₁ ∩ L₂ dilini kabul eden bir sonlu otomat A kuracağız; böylece L₁ ∩ L₂ dilinin düzenli olduğunu göstermiş olacağız.

Bir sözcük hem L₁ hem de L₂ diline aitse dillerin kesişimine aittir. Yani sözcüğü hem A₁ otomatı hem de A₂ otomatı kabul etmelidir. Düzenli dillerin birleşimi için kullandığımız fikrin aynısını kullanacağız; yalnızca son durumlar kümesini değiştireceğiz.

Yöntemin Biçimsel Anlatımı

İki otomatımız var,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

L(A₁) ∩ L(A₂) dilini kabul eden A = ⟨Q, Σ, δ, q, F⟩ otomatını kuruyoruz. Şunlar geçerlidir:

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Geçiş fonksiyonu δ için şu bağıntı geçerli olacaktır:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Örnek

Çift sayıda 1 içeren tüm sözcükleri kabul eden şu A₁ otomatı olsun:

ve tek sayıda 0 içeren sözcükleri kabul eden A₂ otomatı olsun:

Bu dillerin kesişimini kabul eden otomatı kuralım. Bu otomatın durumlar kümesi Q = Q₁ × Q₂ biçimindedir, başlangıç durumu ⟨q₀, p₀⟩ durumudur ve son durumlar F₁ × F₂ kümesidir:

Şimdi geçişleri δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩ olacak biçimde tamamlayalım:

Bu otomatta örneğin ⟨q₀, p₀⟩ durumundan 0 simgesiyle ⟨q₀,p₁⟩ durumuna bir geçiş vardır. Bunun anlamı şudur: A₁ otomatının q₀ durumundan 0 simgesiyle yine q₀ durumuna dönen bir geçişi vardır. A₂ otomatının ise 0 simgesiyle p₀ durumundan p₁ durumuna geçişi vardır.

Otomatı deneyebiliriz. 110 veya 00000 gibi sözcükleri kabul etmelidir (çift sayıda 1 ve aynı zamanda tek sayıda 0 içerirler), ama 11, 111, 1010 gibi sözcükleri kabul etmemelidir.

Kaynaklar

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools