Regüler İfadeler

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

dfa

Soru: M makinesine ait dfa diagramı şekildeki gibidir.

Buna göre aşağıdaki soruları cevaplayın.

a-) M makinesine ait geçiş tablosu oluşturun.

b-) baba, baab, abab, abaaab dizgilerinden hangileri M makinesi tarafından tanınır, belirtin.

c-)L(M) için regüler ifadeyi elde edin.

Çözüm:

a-)

b-)

 baba (tanınmaz)

baab(tanınır)

abab(tanınmaz)

abaaab(tanınır)

c-)

L(M)=b*aa*b(ab*aa*b + ba*b)*