Mooreov automat

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

U teoriji računanja, Mooreov automat je konačni automat u kojem je izlazna funkcija pridružena isključivo trenutnom stanju automata, i ne ovisi o ulazu. Dijagram stanja za Mooreov automat uključuje izlazni znak (simbol) za svako stanje. Uporedi sa Mealyevim automatom, u kojem je funkcija izlaza pridružena i stanju i ulaznom znaku, te na taj način preslikava prijelaze stroja na izlaz.

Ime Mooreov automat vuče korijen od svoga pronalazača: Edwarda F. Moorea, jednog od pionira konačnih automata, koji ih je prvi opisao u radu Gedanken-experiments on Sequential Machines, pp 129 – 153, Automata Studies, Annals of Mathematical Studies, no. 34, Princeton University Press, Princeton, N. J., 1956.

Formalna definicija[uredi | uredi izvor]

Mooreov automat se može definirati kao uređena šestorka: { S, S0, Σ, Λ, T, G } koju čine

  • konačan skup stanja ( S )
  • početno (ili inicijalno) stanje S0 koje je element skupa (S)
  • konačan skup ulaznih znakova (ulazna abeceda ( Σ )
  • konačan skup izlaznih znakova (izlazna abeceda) ( Λ )
  • funkcija prijelaza (T : S × Σ → S) koja preslikava trenutno stanje i ulazni znak u sljedeće stanje
  • izlazna funkcija (G : S → Λ) koja preslikava svako stanje u znak izlazne abecede

Broj stanja u Mooreovom automatu će biti veći ili jednak broju stanja istovjetnog Mealyevog automata

Također pogledajte[uredi | uredi izvor]