Mealyjev 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.
Dijagram stanja jednostavnog Mealyjevog automata

U teoriji računanja, Mealyjev automat je vrsta konačnog automata čija je funkcija izlaza pridružena trenutnom stanju i ulaznom znaku (simbolu). Slijedi da će odgovarajući dijagram stanja sadržavati i ulazni i izlazni znak za svaki brid (granu) prijelaza usmjerenog grafa. Kao suprotnost tome, izlaz Mooreovog konačnog automata zavisi isključivo od trenutnog stanja automata, pri čemu prijelazi nemaju pridružen nikakav ulaz. Međutim, za svaki Mealyjev automat postoji istovjetni Mooreov automat čiji je skup stanja unija skupa stanja Mealyjevog automata i Kartezijevog produkta skupa stanja Mealyjevog automata i ulazne abecede.

Ime "Mealyjev automat" vuče korijene od svoga pronalazača: G. H. Mealya, jednog od pionira konačnih automata, koji ih je prvi opisao u radu A Method for Synthesizing Sequential Circuits, Bell System Tech. J. vol 34, pp. 1045–1079, September 1955.

Formalna definicija[uredi | uredi izvor]

Mealyev automat je 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)
  • izlazna funkcija (G : S × Σ → Λ)

Također pogledajte[uredi | uredi izvor]