dilbilgisi ve diller

by

chomsky hiyerarşisi

en basit şekilde chomsky hiyerarşisi aşağıdaki gibidir.

Tip 0: yinelemeli sıralı diller (kısıtlamasız dilbilgisi)
Tip 1: context-sensitive diller (context-sensitive dilbilgisi)
Tip 2: context-free diller (context-free dilbilgisi)
Tip 3: düzenli (regüler) diller (sağ-doğrusal ve sol-doğrusal dilbilgileri)

Dileri tanıyan modeller ise şöyle:

Tip 0: Turing Makinesi
Tip 1: Doğrusal Sınırlandırılmış Otomat (Linear Bounded Automata)
Tip 2: Pushdown Otomat
Tip 3: Sonlu Otomat(NFA,DFA)

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

Doğru-Yanlış

Aşağıdaki sorulardan hangisinin doğru olup hangisinin yanlış olduğunu belirtiniz.

1-) Eğer bir A diline ait bir DFA varsa bu dil context free dir.

2-) Eğer bir B dili regüler ise context free değildir.

3-)

 dili regüler bir dildir.              

4-) Eğer L dili regüler ise L dili sonludur. 

5-) Bütün diller ya regülerdir ya da context free dir.

Çözüm:

1-) Doğru

2-) Yanlış

3-) Yanlış

4-) Yanlış. Örneğin: {a,b}* regülerdir bir DFA’sı vardır ama sonlu değildir; sonsuz bir kümedir.

5-) Yanlış.

dili ne regülerdir ne de context free dir.

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