dilbilgisi ve diller

by

yeniden dfa :)

Soru: Alfabemiz Σ={0,1,2} den oluşsun. L1={ w € Σ*: w 0 ile başlıyor veya 0 ile bitiyor fakat her iki durum söz konusu değil }

Buna göre L1 dilini tanıyan DFA’yı oluşturun. Açıklayınız.

Not = € (elemanıdır manasına geliyor)

Çözüm:

L1 diline ait  dfa yukaridaki gibidir.

5 tane durumumuz var : q0,q1,q2,q3,q4. Eğer O ile başladıysak O ile DFA yı bitiremeyiz. Bu yüzden O ile q3 durumuna ulaşmayız. Yukardaki gibi  q1 durumuna O ları götürebiliriz. Eğer 1 veya 2 ile başladıysak O ile bitirmemiz gerek. Aksi taktirde şartımız şağlanmaz.

by

türetme kuralları

Aşağıdaki dilbilgilerine karşı gelen birer regüler ifade elde edin.

a-)

S → aA

A → aA | bA | b

———————
b-)

S → aA

A → aA | bB

B → bB | λ

———————

c-)

S → aS | bA

A → bB

B → aB | λ

———————

d-)

S → aS | bA | λ

A → aA | bS

Cevap :

a-)  a(a+b)*b

b-)  aa*bb*

c-)  a*bba*

d-)  (a + ba*b)*

by

CFG

Soru: Aşağıda küme tanımı verilen dillere ait context free grammer leri elde edin.

Dillerin tanımlı olduğu alfabe={0,1}

a-) L1={w| w en az 3 tane 1 içerecek}

b-) L2={w|w uzunluğu tek ve ortadaki sembol 0 olacak}

Çözüm:

a-)

G=<Vn,Vt,P,S>

Vn={S,R}

Vt={0,1}

P:

    S –> R1R1R1R

    R –> 0R | 1R | e

e=epsilon

——————————–

b-)

G=<Vn,Vt,P,S>

Vn={S}

Vt={0,1}

P:

    S –> 0 | 0s0 | 0s1 | 1S0 | 1S1