BİÇİMSEL DİLLER ve ÖZDEVİNİRLER -4

Görsel OpenAI’nin DALL-E modelinden üretilmiştir.

Merhabalar bu yazımda Biçimsel Diller ve Özdevinirler konusunda kaldığım yerden devam edeceğim.

Düzgün Deyimlere Karşı Gelen Sonlu Özdevinirlerin Bulunması

Örnek-1: P₀ = 0+11 deyimine karşılık gelen sonlu özdeviniri çizelim.

Bu deyime karşılık gelen sonlu özdeviniri bulurken, denklemi parçalara ayırıp çözümleyerek ilerleyeceğiz.

Bu yaklaşım, verilen makine için doğru sonuç verir, ancak spesifik olarak P₀ makinesi bu değildir.

• Öncelikle denkleme en dıştan bakıyoruz = 0 + 11
• ‘+’ işareti gördüğümüzde sağı ve solu için iki ayrı işlem yapacağız.
• +’ nın solu için baktığımızda 0 girişi geldiğinde makine çıkışa ulaşmalı.

• +’ nın sağı için baktığımızda 11 girişi geldiğinde çıkışa ulaşmalı.

• Burada, A = {1, A} veya A = {1, B}, B = {1, B} gibi tanımlamalar yerine önce C düğümüne, ardından B düğümüne gitmemizin sebebi, diğer durumların daha fazla durumu kapsıyor olmasıdır. Örneğin, A = {1, B} ve B = {1, B} şeklinde bir tanımlama yapıldığında, makine {1, 11, 111, 1111…} gibi durumları da tanır. Ancak biz yalnızca “11” durumunu istediğimiz için, ekstra bir düğüm ekleyerek sadece bu durumu almayı mümkün hale getirdik.
• Daha sonrasında oluşturduğumuz iki makineyi bağlayalım.

P₀ = 0+11 deyimine karşılık gelen sonlu özdevinir makinesi budur.

Örnek-2: P₁ = (0+101) deyimine karşılık gelen sonlu özdeviniri çizelim.

• Öncelikle denkleme en dıştan baktığımız zaman (x)* durumu bulunuyor. Bu P₁ = { } durumunun çıkış ürettiği anlamına gelir. Bu durumda başlangıç durumunun aynı zamanda çıkış durumu da olması gerektiğini gösterir.

• Denklemin iç durumuna baktığımız zaman 0+10*1 olarak gözükür.
• +’ işaretini sağ ve sol olarak ikiye ayırarak, 0 girişinde çıkışa gitmesini sağlarız.

*Bu makinede ikinci çizim yanlıştır, çünkü P₁ = (x) yapısı bulunuyordu. Bu durumda tekrarlı (recursive) bir çizim yapılması gerekir. Yani işlem tamamlandığında, tekrar başladığımız düğüme dönmeliyiz.* P₁ = (0 + 101)* deyimi {0, 00, 000, …} gibi durumları tanır. Ancak ikinci çizim bu durumları tanımaz.

• +’ işaretinin sol kısmına baktığımız zaman 10*1 durumu için çıkışa ulaşmalı.

• Daha sonrasında oluşturduğumuz iki makineyi bağlayalım.

P₁ = (0 + 101) deyimine karşılık gelen sonlu özdevinir makinesi budur.

Örnek-2: P₂ = (001)(110)*22 deyimine karşılık gelen λ geçişli sonlu özdeviniri çizelim.

• P₂ makinesinde, son durumun mutlaka “22” ile bitmesi gerekmektedir ve bu yapı tekrarlı (recursive) olmadığı için başlangıç düğümü bitiş düğümü değildir; “22” ile bitiş durumuna ulaşılır.

• Daha sonrasında (001)(110)* kısmını ikiye ayırıp λ ile bağlayalım.

Bu makinede λ-geçişi kullanmak zorunda değiliz; ancak kullanırsak, daha sade ve estetik bir makine elde ederiz.

• Daha sonrasında iki makineyi birleştirelim.

*P₂ = (001)(110)22 deyimine karşılık gelen λ geçişli sonlu özdevinir makinesi budur.**

Bu yazımda, düzgün deyimlerin tanımını yaparak bu deyimlerin sonlu özdevinirlere nasıl karşılık geldiğini inceledik. Bu dönüşüm sürecinin altında yatan kuralları ve adımları açıkladım. Son olarak, bu konuyla ilgili farklı soru tiplerini çözerek, konuyu daha derinlemesine işledik.

Umarım faydalı bir kaynak olmuştur. Sonraki yazımda görüşmek üzere.

https://samedsonkaya.com/