Postup redukce Moore - Moore reduction procedure

V počítačové vědě je Postup redukce Moore je metoda používaná pro Minimalizace DFA.

Koncept má začít předpokládat, že každý stát může být schopen kombinovat s každým jiným státem, poté oddělit rozlišitelné stavy do samostatných skupin zvaných ekvivalenční oddíly. Pokud žádné další oddíly ekvivalence neobsahují rozlišitelné stavy, stavy zbývající ve stejné skupině jako ostatní stavy se spojí. Oddíly ekvivalence jsou očíslovány počtem kroků, které byly potřeba k dosažení tohoto bodu. 0. oddíl obsahuje všechny stavy v jedné skupině, 1. oddíl obsahuje stavy seskupené podle nich výstupy pouze. Každý oddíl má od té doby seskupení, která jsou založena na tom, do které skupiny z předchozího oddílu spadl další stav těchto států. Postup je dokončen, když oddíl n je stejný jako oddíl .

Státy, které jsou rozlišitelné na EU kth se nazývá oddíl k-rozlišitelný státy. Státy, které jsou ve stejné skupině na EU kth se nazývá oddíl k-ekvivalent. Všimněte si, že uvádí, že jsou k-ekvivalent v jednom bodě nemusí být nutně ekvivalentní stavy, protože je lze rozdělit do samostatných skupin ve vyšším oddílu.

Postup je následující:

  1. oddělené stavy do skupin, které mají stejný okamžitý výstup pro stejný aktuální vstup,
  2. rozlišit státy, jejichž další stavy jsou v různých skupinách,
  3. přeskupte stavy a opakujte výše uvedený krok, dokud nebudou rozlišitelné žádné další stavy.

Viz také

Reference

  • Ralf Lämmel; Joost Visser; João Saraiva (8. října 2008). Generativní a transformační techniky v softwarovém inženýrství II: Mezinárodní letní škola, GTTSE 2007, Braga, Portugalsko, 2. – 7. Července. 2007, revidované dokumenty. Springer. str. 483–. ISBN  978-3-540-88643-3.