C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?

C={w|w eşit sayıda 0 ve 1 içerir} dili düzenli mi, değil mi?

Bir dilin düzenli olup olmadığını anlamak için pompalama önsavı(pumping lemma) şartlarını sağlaması gerekmektedir. Bir dilin düzenli olmadığını en başta o dili düzenli kabul ederek pompalama önsavı(pumping lemma) şartlarını sağlayamaması durumunda olmayana ergi(proof by contradiction) ile ispat ederiz.

Pompalama Önsavı (Pumping Lemma) şartları:
-A bir dil ise, p pompalama uzunluğu ise bu dile ait bir s ifadesi, s=xyz şeklinde ifade edilebilmelidir ve her i>=0 için xy^iz elemanıdır A dilinin, |y|>0 ifadenin y bölümü boş olamaz, |xy|<=p ifadenin xy kısmı p uzunluğuna eşit ya da küçük olmak zorundadır. 1.Adım: C dili düzenlidir. 2.Adım: Dilden üretilen ifademiz O^p1^p olsun. 3.Adım: p uzunluğundaki bir s ifadesi s=xyz şeklinde parçalanmalıdır. 4.Adım: x ve z boş olursa y=O^p1^p olabilir. Bu durumda her i>=0 için xy^iz C dilinin elemanıdır.
5.Adım: |xy|<=p şartında ise s=O^p1^p olduğundan y burada sadece 0 lardan oluşabilir. Böylece xyyz ifadesi C diline ait olmaz. Böylece pompalama işlemi gerçekleştirilemez ve ifadenin düzenli olmadığı anlaşılır.

Etiketler: , , ,

1 Yorum

  1. Buna ek olarak, birinci şart, xy^iz E A ;
    i=2 olsun. CASE 1 =00000111, CASE 2 =0011111111 ya da CASE 3 = 000101010111. Ancak CASE 1,2 ve 3 A dilinde değildir.

Yorum Yapın