Sonlu Otomat Nedir?

0 beğenilme 0 beğenilmeme
261 kez görüntülendi

Şu anda kullandığımız bilgisayarlarla ilişkisi nedir?

1, Kasım, 2017 Teorik Bilgisayar Bilimi kategorisinde Salih Durhan (1,287 puan) tarafından  soruldu

2 Cevaplar

1 beğenilme 0 beğenilmeme

Esasen iki tür sonlu otomata (finite automaton) bulunmakta : belirli (deterministic) ve belirli olmayan (non-deterministic) sonlu otomata. İlkini açıklamaya çalışayım : 

Bir belirli sonlu otomata $M$ 5 bileşenden oluşuyor 

(i) : sonlu bir hal kümesi $Q$

(ii) : sonlu bir alfabe $\Sigma$

(iii) : bir $\delta : Q\times\Sigma\rightarrow Q$ fonksiyonu

(iv) : bir başlangıç hali : $q_0\in Q$

(v) : ve bir final halleri kümesi $F\subseteq Q$

ve şu şekilde çalışıyor : 

$M$'e bir kelime $w$ verilir. Burada kelime alfabenin elemanları kullanılarak yazılmış sonlu bir dizidir. Yani $w=(l_1,...,l_n)$ ve $l_i\in\Sigma$. Daha sonra adım adım $\delta$ fonksiyonu kullanılarak yeni haller üretilir, yani adım adım $q_i=\delta(q_{i-1},l_i)\in Q$ elemanları hesaplanır. Eğer sonunda ulaştığımız hal, $q_n$, final hallerinden biriyse, yani $q_n\in F$ ise, $w$ kelimesi $M$ tarafından kabul edilir denir. 

$W$ kümesi $\Sigma$ alfabesi kullanılarak yazılabilecek olan tüm kelimeler olsun (boş kelime de dahil olmak üzere). $L$ kümesi de $M$ belirli sonlu otomatasının kabul ettiği tüm kelimeler olsun. Bu $L$ kümesi $W$ kümesinin bir altkümesi. $L$ boş olabilir, tüm $W$ olabilir, çok ilginç başka şeyler de olabilir. $L$ kümesine $M$'in düzenli dili deniyor (regular language).

Arka plandaki fikir şu : 

$M$ ilkel bir makineyi temsil ediyor. Makinenin üzerinde sadece yelkovanı olan bir saat var. Başlangıçta yelkovan belirli bir sayıyı göstersin (saatin gösterebildiği sayılar $Q$ ile ve yelkovanın başlangıçta gösterdiği sayı $q_0$ ile temsil ediliyor). Bu makineye ard arda birtakım girdiler veriyorsunuz, tabii ki bu girdiler makinenin anlamaya programlandığı girdiler olmak zorunda (bu girdiler $\Sigma$ alfabesi ile temsil ediliyor). Makine de verilen girdiye bakıp yelkovanın gösterdiği sayıyı değiştiriyor (makinenin girdi alıp yelkovanın konumunu değiştirmesi $\delta$ fonksiyonu ile temsil ediliyor). Bütün bu işlemin sonunda yelkovan belirli bir sayıyı gösteriyor olacak. Eğer bu sayı önceden belirlediğimiz güzel sayılardan ($F$ kümesinin elemanları) biri ise, bu girdi $M$ makinesi için anlamlı bir girdi. Eğer değilse, makinenize girdiğiniz girdi makineniz için anlamsız, saçma bir girdi. Hesap makinesine $elma+armut$ işlemini girmek gibi.

Şimdi öyle bir belirli sonlu otomata tasarlayalım ki $0$ ve $1$'lerden oluşan bir dizi verildiğinde bu dizide $0$'ın olmadığını kontrol etsin. Yani örneğin makinemiz $11111111$ dizisi verildiğinde bu dizide $0$ olmadığını anlasın (düzenli diller terminolojisini kullanırsak şu manaya geliyor : $M$'in düzenli dili, içinde en az bir kere $0$ içeren ikili diziler) : 

(i) Önce alfabemizi belirleyelim. Verilen dizi $0$ ve $1$'lerden oluştuğuna göre, cevap belli : $\Sigma=\{0,1\}$.

(ii) $Q$ haller dizisini pek çok farklı şekilde seçebiliriz. En basit olanı şu $Q=\{e,h\}$. Bu harfleri evet ve hayır kelimelerinin baş harfleri olsun diye seçtim.

(iii) Başlangıç hali $q_0=h$ olsun. Yani makinemiz dizide $0$ olmadığı varsayımıyla ile başlayacak.

(iv) Final halleri kümesi $F=\{e\}$ olsun. Yani makinemiz sadece sonunda $e$ haline vardığı kelimeleri kabul edecek.

(v) Şimdi de makinenin asıl kısmı olan $\delta$ fonksiyonunu yazalım : 

$Q\times\Sigma$ kümesi şu : $\{(e,0),(e,1),(h,0),(h,1)\}$. Fonksiyonu şöyle tanımlayalım : 

$\delta(e,0)=e$

$\delta(e,1)=e$

$\delta(h,0)=e$

$\delta(h,1)=h$.

Makinemiz tamamlandı. Şimdi çalışıp çalışmadığına bakalım. Bunun için $\delta$ fonksiyonunu incelememiz lazım. Eğer makine $e$ haline bir kere girdiyse (ki amacımızı hatırlarsak, bu dizinin $0$ içermesi manasına geliyor), bir daha $e$ halinden çıkmıyor çünkü $\delta(e,0)=\delta(e,1)=e$. Ki bu da mantıklı, çünkü makine verilen dizide bir kere $0$ görmüşse, artık bu dizide $0$ var demektir, dizinin devamında ne olursa olsun $e$ hali $e$ hali olarak kalacaktır. Fakat başlangıç halimiz $h$. Hangi durumda $h$ halinden $e$ haline geçiyoruz? Hatırlayalım : $\delta(h,0)=e$. Yani makine $0$'ı gördüğü zaman $h$ halinde ise $e$ haline geçiyor. Ki bu da makinenin amacına uygun. Henüz $0$ görmediyse makine, $h$ durumunda bekliyor ve $0$'ı görünce de $e$ durumuna geçiyor.

Bir örnekte deneyelim, dizimiz $111001$ olsun :

1. Adım : $111001$

Makine başlangıç hali olan $h$ halinde.

2. Adım : $11001$

$1$ sayısını okuduk. $\delta(h,1)=h$ olduğu için, makine hala $h$ halinde bekliyor.

3. Adım : $1001$

İkinci $1$ sayısını okuduk. Makine hala $h$ halinde.

4. Adım : $001$

Üçüncü $1$ sayısını okuduk. Makine hala $h$ halinde.

5. Adım : $01$

$0$ sayısını okuduk. Makine $h$ halindeydi. Yeni halimiz $\delta(h,0)=e$. Bundan sonra hep $e$ halinde kalacak.

6. Adım : $1$

Makine $e$ halinde.

7. Adım : 

Makine $e$ halinde.

Final halleri kümemiz $\{e\}$ olduğu için ve en son gördüğümüz hal $e$ olduğu için $111001$ dizisi makinemiz tarafından kabul ediliyor.

Peki belirli sonlu otomataların önemi nedir, bilgisayarlarla ilişkisi nedir? Belirli sonlu otomatalar daha önceden de dediğim gibi ilkel makineleri temsil ediyor. Önemleri ise sınırlı bir işlem gücü ile çözülebilecek birtakım problemleri temsil ediyor olmaları. Açıklamaya çalışacağım. Çok önemli bir soru şu : verilen bir sonlu alfabe $\Sigma$ ve $\Sigma$ kümesi kullanılarak yazılabilecek bütün sonlu kelimelerin kümesi $W$'yu düşünelim. $P(W)$ ise $W$ kümesinin kuvvet kümesini belirtiyor olsun. Acaba $P(W)$ kümesinin hangi elemanları bir belirli sonlu otomatanın düzenli dilidir? Örneğin $\Sigma=\{0,1\}$ için içinde $0$ içeren sonlu diziler kümesinin üstteki belirli sonlu otomatanın düzenli dili olduğunu biliyoruz. Acaba hangi tipteki kümeler düzenli dil olabilir? Bir teorem : $L=\{\emptyset,01,0011,000111,00001111,...\}$ kümesi hiçbir sonlu otomatanın düzenli dili olamaz. Kanıtını burada vermeyeceğim fakat içgüdüsel olarak sebebi, bu kümeyi tanıması için ilkel bir makinenin sonsuz hafızaya sahip olması gerekmesi. Tabii ki modern bilgisayarlarda herhangi bir programlama dili kullanarak bu dili tanıyacak bir algoritma kolaylıkla yazabilirsiniz. Bunun sebebi de bilgisayarları temsil eden kavramın belirli sonlu otomatalar değil, Turing makineleri olması.

Not : İngilizceden Türkçeye yapılan çeviriler bana aittir, Türkçedeki doğru kavramlar olup olmadığından hiç emin değilim.


 

30, Kasım, 2017 Riemann (310 puan) tarafından  cevaplandı
30, Kasım, 2017 Riemann tarafından düzenlendi
0 beğenilme 0 beğenilmeme

Şu anda kullandığımız bilgisayarlarla ilişkisi nedir?

sorusunu yanıtlamaya çalışayım. Bunun için önce işlem ve işlem ünitelerini anlamak gerek

\(2+2\) işlemini ele alalım bu işlem bir işlem ünitesi gözünden \(toplama(x,y)=x+y\)  olmak üzere; \(toplama(2,2)\) şeklinde değerlendirilir yani input sayısı sınırlıdır aynı şekilde output sayısıda yani \(2+2+2\) işlemi bu işlem ünitesi ile çözülemez bu sorunu aşmanın 2 yolu vardır.

  1. işlem ünitesini arttırmak (daha fazla işlemci):

    \(toplama_1(x,y)=x+y\),
    \(toplama_2(x,y)=x+y\) olmak üzere
      
    \(toplama_1(2,toplama_2(2,2))\)

    $\mathcal{0}(1)$ zaman karmaşıklığı (Big O notation)(problemi tek adımda çözdük demek)

  2. işlemi parçalamak tarihsel kayıt tutarak aynı üniteyi kullanmak (daha fazla hafıza):

    \(toplama(x,y)=x+y\),
    \(:= işlemi \) \( f(x,y)=\) \(“y\) \(x\) \(olmak\) \( üzere”\) olmak üzere
    (C dilinde “=” (atama operatörü) ve “==” (eşitlik kontrolcüsü) arasındaki fark)

    \(sonuc := toplama(2,2)\),
    \(sonuc := toplama(2,sonuc)\)

    $\mathcal{0}(n)$ zaman karmaşıklığı (problemi \(n \pm c(sabit)\) adımda çözdük demek)
Peki sorarsanız bu adam ne anlatıyor bütün bunların sonlu otomata ile ne alakası var?
sonlu otomatada alfabeniz ile işlem yapar stateler ile de hafızada tuttuğunuzu düşünürseniz

işlem uzayınıza 10 tabanında sayılar derseniz ve sisteme 5 adet 10 tabanında sayı tutabilen hafıza elemanı eklerseniz

hafızanız duruma göre;
00000  -> boş
00001
00005
00304

gibi olabileceğini hayal ederseniz ortaya 99999 anlamlı 1 adet boş state çıkar
başlangıç durumunuzu \(0\) olarak düşünün
alfabeniz ise 
\(+0,+1,+2,+3,+4,+5,+6,+7,+8,+9\)
her state ise final hali olursa
state geçişlerini ise işlem sonucuna göre ayarlarsanız
toplama fonksiyonunu elde etmiş olursunuz
otomatamız örneğin \(“1+3+2+9+3+6+0”\) ifadesini güzelce kabul eder ve sonlandığı state de sonuç olur.

\(-1,-2,-3,-4,-5,-6,-7,-8,-9\) alfabemize bunları da eklersek ve gerekli düzenlemeleri yaparsak ortaya basit bir hesap makinesi bile çıkar
bu arada otomata çizimlerine aldanıp fiziksel nodelarınızın olması gerektiğini düşünmeyin sonlu sayıda durumunuzu nasıl tutacağınız size kalmış 

buradan da şu sonuca ulaşabiliriz günümüz bilgisarları sonlu otomatlardır
Neden?
Ram üzerinde sadece sonlu sayıda durum tutabilirsiniz çünkü. bu kadar net


günümüz bilgisayarları turing machine değil miydi?

ne yazık ki

Neden?
Turing machine Alan Turing tarafından tüm hesaplama işlemlerini kapsamak üzere tasarlanmış
elde olan işlem ünitelerine ve SONSUZ sayıda hafıza elemanına sahip FARAZİ bir düşünsel makinadır. 
Amacı düşünsel süreci kolaylaştırmak ve sonlu otomatların engellerine takılmadan düşünebilmektir
günümüz bilgisayarları devasa hafıza ünitelerine sahip bir insanın kolaylıkla turing machine gibi algılayabileceği sonlu otomatlardır ama ne yazık ki 32 GB Ram i olan bir makine ile boyutu 32 GB olan 2 sayıyı toplayamazsınız bu fiziksel engel 128 GB Ram i olan makineler için geçerli olmayacaktır bu da bilgisayarlara neden turing machine gibi davranıyor olma sebebimiz bilgisayarlara Eventually(önünde sonunda) Turing Machine de denilebilir :)

bu arada turing complete olanlar bilgisayarlar değil dillerdir çünkü diller ifade biçimleridir örneğin günümüzde 1024 TB lık Rame sahip bir makinede çalışacak bir program yazılabilir yada daha fazla ama günümüz makineleri bunları çalıştıramaz gelecekte belki

sonsuz rame sahip bir bilgisayar turing machinedir sanılanın aksine günümüz bilgisayarları turing machineden daha gelişmiş değildir

Turing machine: hesaplanabilir her problemi çözer. (Zaman probleme göre değişir) 
Bilgisayar: kapasitesi yeten hesaplanabilir her problemi çözer.(Zaman probleme göre değişir)

yani özetle günümüz bilgisayarları turing machine gibi davranılan turing machine'e en yakın şeylerdir ama özlerinde aşırı gelişmiş birer sonlu otomattırlar bu biraz asla gerçek bir kare çizemeyecek olduğunuz gerçeği gibidir kare mükemmel bir soyutlamadır sizin çizdiğiniz hiç bir şekil kare gibi olamayacaktır ama masa yapan bir marangoz yine de kare için geçerli işlemleri kendi mükemmel olmayan masasına uygular bizde elimizdeki aşırı gelişmiş sonlu otomatlarımıza mükemmel turing machine gibi davranıyoruz çünkü aralarındaki fark bizim için ihmal edilebilir


Düzeltme: Ram olarak yazdığım bölümlerde kastım bilgisayarın sahip olduğu bütün hafıza elemanları Harddisk Network gibi hafıza eklemeleri ile dahi sonlu bir uzayda matematik icra edersiniz.


13, Mart, 13 aernile (15 puan) tarafından  cevaplandı
...