Month: October 2010

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

Kümeler

Soru:

{1, 2, 3, 4, 5, 6, 7, 8} kümesinin ardışık sayılar içermeyen kaç farklı altkümesi vardır?

Çözüm:

Öncelikle kümeyi ardışık sayılar içermeyen alt kümelere ayrıştıralım. Daha sonra yeni oluşan kümelerden alt küme sayısını elde edelim.

{1, 3, 5, 7}      alt küme sayısı = 16

{2, 4, 6, 8}      alt  küme sayısı = 16

1 –> {4, 6, 8} alt küme sayısı = 8

Oluşan her alt kümeye 1 eklenir.

3 –> {6, 8}     alt küme sayısı = 4     

Oluşan her alt kümeye 3 eklenir.

5 –> {2, 8}     alt küme sayısı = 4

Oluşan her alt kümeye 5 eklenir.

7 –> {2, 4}     alt küme sayısı = 4

Oluşan her alt kümeye 7 eklenir.

1,3 –> {6, 8}  alt küme sayısı = 4

Oluşan her alt kümeye 1,3 eklenir.

1,5 –> {8}      alt küme sayısı = 2

Oluşan her alt kümeye 1,5 eklenir.

1,7 –> {4}      alt küme sayısı = 2

Oluşan her alt kümeye 1,7 eklenir.

1,3,5 –> {8}   alt küme sayısı = 2

Oluşan her alt kümeye 1,3,5 eklenir.

3,5 –> {8}      alt küme sayısı = 2

Oluşan her alt kümeye 3,5 eklenir.

5,7 –> {2}      alt küme sayısı = 2

Oluşan her alt kümeye 5,7 eklenir.

Oluşan alt kümelerin hepsinde boş kümede oluşur. Bunları elememiz gerekir bir tanesi hariç.

16 + 15 + 7 + 3 + 3 + 3 + 3 + 1 + 1 + 1 + 1 + 1 = 55