:::: MENU ::::
Hesaplama Teorisi

Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?

Belirsizlik (Ambiguity) nedir? Bir örnekle açıklayınız?
Bir L(G) içerikten bağımsız gramerinden (context-free grammar) üretilmiş w ifadesi için birden fazla türetme ağacı (derivation tree) oluşturulabiliyorsa bu tip gramere belirsiz(ambigious) denir ve bu durumun oluşmasına Belirsizlik (Ambiguity) ismi verilir.

Örneğin:
X → X+X | X*X | X | a gramerini belirsiz midir değil midir?
‘a+a*a’ ifadesini türeterek gösterelim:

Soldan türetme ile: X → X+X → a+X → a+X*X → a+a*X → a+a*a

soldan-turetme-agaci

Sağdan türetme ile: X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

sagdan-turetme-agaci

Aynı ifade 2 farklı türetme ağacı ile türetilebildiğinden belirsizlik(ambiguity) vardır.



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.


Bir otomatın düzenli ifadesini (regular expression) yazınız?

Aşağıdaki otomatın düzenli ifadesini(regular expression) yazınız?

DFA

Çözüm:

DFA-RE

Arden Teoremi ile çözmeye çalışalım: Not: Henüz çözemedim
q1=q2a+q3b+null
q2=q1a+q2b+q3a
q3=q1b
oluşturulur.

q2=q1a+q2b+q3a
q2=q1a+q2b+(q1b)a
q2=q1(a+ba)+q2b
q2=q1(a+ba)+b*

q1=q2a+q3b+null
q1=(q1(a+ba)+b*)a+(q1b)b+null
q1=q1((a+ba)+b*))a+bb)+null
q1=q1((a+ba)+b*))a+bb)+null
q1=null((a+ba)+b*))a+bb)*
q1=((a+ba)+b*))a+bb)*


Sayfalar:12345678