Mealyev automat

Izvor: Wikipedija
Jump to navigation Jump to search

U teoriji izračunljivosti, Mealyev automat (ili Mealyev stroj) 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 ovisi isključivo o trenutnom stanju stroja, pri čemu prijelazi nemaju pridružen nikakav ulaz. Međutim, za svaki Mealyev automat postoji istovjetni Mooreov automat čiji je skup stanja unija skupa stanja Mealyevog automata i Kartezijevog produkta skupa stanja Mealyevog automata i ulazne abecede.

Ime "Mealyev automat" vuče korijene od svoga promicatelja: 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 VE | uredi]

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 × Σ → Λ)

Vidjeti također[uredi VE | uredi]