context-free grammer sorusu

[freemaniacss]

bir sorum var
-design a context-free grammer over alphabet {0,1} that describes the language of regular expression 0*1(0U1)*

bu soruyu ben nasıl yapıcam,hangi yolla?bi el atarmısınız şu soruya rica etsem:D NFA tarzında yapılmıcak,peki nasıl yapılcak bu soru?

[freemaniacss]

yokmudur computing den anlayan bi paticik.

[fizban]

-design a context-free grammer over alphabet {0,1} that describes the language of regular expression 0*1(0U1)*

oyle bir dil olarak ki önce istediği kadar 0 alacak
sonra 1 aldığı yerde duracak
sonra ne isterse alacak, bize ne

S -> A1B
A -> A0
A -> € (empty diye düsün bunu)
B -> B | 0 | 1 | €

bitti işte.

[Ardeth]

vat?

[freemaniacss]

S -> A1B
A -> A0
A -> € (empty diye düsün bunu)
B -> B | 0 | 1 | €

fizban bu yanlış değil mi :D
bize istediği kadar 0 alsın,ardından 1 kesin alsın,ardından olan kısmını yapamadım.Union olunca ne yapıcam ?
Senin yaptığında mesela seçelim S->A1B->A01B->A001B->A0010->0010
bu kabul oluyo sonuçta.

[fizban]

(0 birleşim 1)* demek, 0 veya 1'lerden oluşan herhangi bir string demek.

[freemaniacss]

yok yok yanlış anladın union normalde öyle demekte,böyle language design larda başka bi işe yaramıyo dimi.yani stringimiz 0000100000 olsa kabul edicek,peki 000010000111 olsa kabul edermi?

[fizban]

evet
hatta bak: http://www.cs.duke.edu/csed/jflap/tutorial/regular/index.html union işareti yerine + kullanılıyor. 6. maddeye bak.

alfabe {0,1} ise (0U1)* bütün set demek zaten.

bir de bu tip soruları çözerken daima uç durumlara bak, mesela senin grammerinin dili yalnızca "1"i kabul ediyor mu ? keza etmeli. çünkü başta 0* var, e oradan boş string gelebilir, sonra (0u1)* dan da boş string gelebilir, tek şart ortada bir adet 1 olması.

[freemaniacss]

çok sağol anladım olayı.

[Ardeth]

fizban +1

[riglous]

abstract algebra ftw!

[Cd-]

otomata

[freemaniacss]

bu arada ,fizbanın yaptığını biraz evrim geçirttim.Fizbanın yaptığı hala yanlış geliyor bana,ben böyle yaptım cevabından yola çıkarak,
S -> A1B
A -> A0 | €
B -> B0 | B1 | €

böyle daha mantıklı ve düzenli geldi

[fizban]

B -> BB | 0 | 1 | € diyecektim, yanlıs olmus benim o yazdıgım hakikaten. seninki dogru simdi eet.

[senko]

olm nasi grammer lan bu?
nukleer fizik konusu mu bu?

[Ardeth]

riglous said:

abstract algebra ftw!

abstract algebra'nın tırnağı olmuş bu daha çok

aslında demek istediğim, matematik bölümünden 2 bilgisayar bölümünden 1 adet olmak üzere soyut cebir dersi aldım bunu görmedim

[freemaniacss]

Hesaplama Kuramı olarak geçiyo ders.Computing Theory.İlginç bir ders,bunlar yine basit olanları zaten.Saçma sapan pumping lemma,turing machine,push-down automata soruları falan var,kastırıyo baya:D

[Cd-]

Biz de direk Formal Languages and Automata Theory diye geçiyo. Çok sıkıcı bi dersti gerçi takip edince eğlenceli gibi geliyo..derslere gitmek lazım.

[senko]

adini soyleyince bende hatirladim dersi, hic girmeden gectiydim zaten (kih kih)

ama bi ise yaramayan bi ders gereksiz zaten muhendisler icin.

[fizban]

computer science'ın temeli bu ders.

[senko]

muhendisler icin dedim zaten. cs'ciler alsin.

[Mirage]

compiler yapımının temeli hatta