

Sınav sorusu gibi olmuş. Sonlu durum makineleri olarak bilinen otomatlar belli bir alfabeden (örneğin a ve b harflerinden oluşan bir alfabe) türetilen girdileri alır. Bu girdide okuduğu her değere göre içerisindeki durumlar arasında geçiş yapar. Örneğin x ve y durumları olabilir. Bunlardan birisi başlangıç durumu olacak şekilde makine tasarlanır ve x durumunda a geldiğinde y 'ye geç ve b geldiğinde x 'te kal gibi durum geçişleri tanımlanır. Bu durum geçişleri tanımlandıktan sonra belli durumlar kabul durumları olarak belirlenir (mesela x kabul durumu olabilir) ve girdide okunan değerlerin tamamı bittikten sonra kabul durumunda biterse bu makine bu girdiyi tanımış olur. Tanınan kuralların hepsini birleştirdiğimiz zaman dil ortaya çıkar. Örneğin her a 'dan sonra b içeren bir dil tanımlanırsa bu dili kabul eden makine "ababbbb" gibi bir girdiyi kabul etmeli ve "aabb" gibi bir girdiyi kabul etmemelidir. Sonlu durum makinesi tasarlamak için kullanılan iki yöntem vardır. Deterministik yöntemde her durumda her giriş için geçişler tanımlanmıştır. Örneğin x durumunda a veya b gelirse ne olacağı bellidir. Nondeterministik otomatlarda ise her durum ifade edilmeyebilir ve "e" dediğimiz boş durum kullanılabilir. Örneğin x durumunda b gelirse hiç bişey olmaması için bu geçiş tanımlanmayabilir. Yada x durumundan hiç bi girdi gelmeden y durumuna geçilmesi için "e" geçişi kullanılabilir. Özetle otomatlar belirli bir alfabeden türetilen girdileri alır, bu girdiye göre durumlar arasında geçişler yapar ve girdinin kabul edilip edilmeyeceğini söyler. Bu aynı zamanda dil oluşturma işlemidir.
cevaplandı: 19 Eki '12, 09:31
numankaraaslan