Moore gép - Moore machine

Az elméleti számítás , a Moore gép egy véges állapotú gép , amelynek kimeneti értékek határozzák csak a jelenlegi állapot . Ez ellentétben áll egy Mealy géppel , amelynek kimeneti értékeit mind az aktuális állapota, mind a bemenetei értékei határozzák meg. A Moore-gép Edward F. Moore-ról kapta a nevét , aki egy 1956-os cikkben mutatta be a koncepciót: „ Gedanken-kísérletek a szekvenciális gépeken”.

Formális meghatározás

A Moore-gép meghatározható hatkettősnek, amely a következőkből áll: ${\ displaystyle (Q, q_ {0}, \ Sigma, O, \ delta, G)}$

• Véges halmazállapot ${\ displaystyle Q}$
• Kezdő állapot (más néven kezdeti állapot), amely a${\ displaystyle q_ {0}}$${\ displaystyle Q}$
• Véges halmaz, az úgynevezett bemeneti ábécé ${\ displaystyle \ Sigma}$
• Véges halmaz, az úgynevezett kimeneti ábécé ${\ displaystyle O}$
• Átmeneti függvény, amely leképezi az állapotot és a bemeneti ábécét a következő állapotra${\ displaystyle \ delta: Q \ times \ Sigma \ rightarrow Q}$
• Egy kimeneti függvény, amely minden állapotot leképez a kimeneti ábécére${\ displaystyle G: Q \ rightarrow O}$

Egy Moore-gép korlátozott típusú véges állapotú jelátalakítónak tekinthető .

Vizuális ábrázolás

asztal

Az állapotátmeneti táblázat egy bemenet és egy állapot viszonyát bemutató táblázat.

Diagram

Az állapot diagramot egy Moore gépnek vagy Moore rajz egy diagram, amely összekapcsolja egy kimeneti értéket minden állam. Moore gép output termelő.

Kapcsolat Mealy gépekkel

Mivel a Moore és a Mealy gépek egyaránt végesállapotú gépek, egyformán kifejezőek: bármelyik típus felhasználható egy szabályos nyelv elemzésére .

A különbség a Moore gépek és a Mealy gépek között az, hogy az utóbbiakban az átmenet kimenetét az aktuális állapot és az áram bemenetének kombinációja határozza meg ( bemenetként ), szemben csak az aktuális állapottal ( mint bemenet a ) . Amikor képviselteti magát, mint az állami diagram , ${\ displaystyle S \ times \ Sigma}$${\ displaystyle G}$${\ displaystyle S}$${\ displaystyle G}$

• Moore-gépnél minden csomópontot (állapotot) kimeneti értékkel jelölünk;
• egy Mealy gépnél minden ív (átmenet) kimeneti értékkel van ellátva.

Minden Moore gép egyenértékű a Lisztes gép azonos állapotok és átmenetek és a kimeneti funkció , amely úgy az egyes állami bemenetpár és a hozamok , ahol az „s kimeneti funkció és az ” s átmeneti függvény. ${\ displaystyle M}$${\ displaystyle G (s, \ sigma) \ rightarrow G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ displaystyle (s, \ sigma)}$${\ displaystyle G_ {M} (\ delta _ {M} (s, \ sigma))}$${\ displaystyle G_ {M}}$${\ displaystyle M}$${\ displaystyle \ delta _ {M}}$${\ displaystyle M}$

Azonban nem minden Mealy-gépet lehet átalakítani egyenértékű Moore-géppé. Egyeseket csak szinte egyenértékű Moore-géppé lehet átalakítani , a kimenetek időben eltolódnak. Ez annak köszönhető, hogy az állapotcímkék párosulnak az átmeneti címkékkel a bemeneti / kimeneti párok kialakításához. Vegyünk egy államról államra való átmenetet . Az átmenetet okozó bemenet felcímkézi az élt . Az adott bemenetnek megfelelő kimenet az állapot címkéje . Figyelje meg, hogy ez az átmenet forrásállapota. Tehát minden bemenetnél a kimenet már rögzített, mielőtt a bemenet beérkezne, és kizárólag a jelenlegi állapottól függ. Ez E. Moore eredeti definíciója. Gyakori hiba az állapot címkéjét kimenetként használni az átmenet során . ${\ displaystyle s_ {i} \ rightarrow s_ {j}}$${\ displaystyle s_ {i}}$${\ displaystyle s_ {j}}$${\ displaystyle s_ {i} \ rightarrow s_ {j}}$${\ displaystyle (s_ {i}, s_ {j})}$${\ displaystyle s_ {i}}$${\ displaystyle s_ {j}}$${\ displaystyle s_ {i} \ rightarrow s_ {j}}$

Példák

Típusok a bemenetek / kimenetek száma szerint.

Egyszerű

Az egyszerű Moore-gépek egy bemenettel és egy kimenettel rendelkeznek:

• széldetektor segítségével XOR
• bináris összeadó gép
• ütemezett szekvenciális rendszerek (a Moore gép korlátozott formája, ahol az állapot csak akkor változik, amikor a globális órajel változik)

A legtöbb digitális elektronikus rendszert ütemezett szekvenciális rendszerként tervezték . Az órás szekvenciális rendszerek a Moore-gép korlátozott formája, ahol az állapot csak akkor változik, amikor a globális órajel változik. Az aktuális állapot jellemzően papucsokban van tárolva , és egy globális órajel csatlakozik a papucsok "óra" bemenetéhez. Az órás szekvenciális rendszerek az egyik módja a metastabilitási problémák megoldásának. Egy tipikus elektronikus Moore-gép kombinációs logikai láncot tartalmaz az aktuális állapot kimenetekké dekódolásához. Abban a pillanatban, amikor az aktuális állapot megváltozik, ezek a változások hullámzanak ezen a láncon keresztül, és szinte azonnal frissül a kimenet. Vannak olyan tervezési technikák, amelyek biztosítják, hogy a kimeneteken ne forduljon elő hiba az adott rövid időszak alatt, miközben ezek a változások végig hullámzanak a láncon, de a legtöbb rendszert úgy tervezték, hogy a rövid átmeneti idő alatt bekövetkező hibákat figyelmen kívül hagyják vagy lényegtelenek. A kimenetek ezután a végtelenségig változatlanok maradnak (a LED-ek világítanak , az áram a motorokhoz csatlakozik, a mágnesszelepek feszültség alatt maradnak stb.), Amíg a Moore-gép újra állapotot nem vált.

Dolgozott példa

Egy szekvenciális hálózatnak van egy bemenete és egy kimenete. A kimenet 1-es lesz, és ezután 1 marad, ha legalább két 0 és két 1 történt bemenetként.

Példa moore gépre

A jobb oldalon egy Moore-gép látható, amelynek kilenc állapota van a fenti leíráshoz. A kezdeti állapot A állapot, a végső állapot pedig I. állapot. Ennek a példának az állapota táblázata a következő:

Összetett

A bonyolultabb Moore-gépek több bemenettel és több kimenettel is rendelkezhetnek.

Gedanken-kísérletek

Moore " Gedanken-kísérletek szekvenciális gépeken " című cikkében az automatákat (vagy gépeket) úgy definiálják, hogy állapotuk, bemeneti és kimeneti szimbólumuk van. Kilenc tétel bebizonyosodott a felépítéséről és azokkal végzett kísérletekről . Később a " gépek" Moore gépek néven váltak ismertté. ${\ displaystyle (n; m; p)}$${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle p}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

A cikk végén, a "További problémák" szakaszban a következő feladat szerepel:

A másik közvetlenül követendő probléma a 8. és 9. tételben megadott határok javítása.

Moore 8. tétele a következőképpen fogalmaz meg:

Adott egy tetszőleges gép , amelynek két állapota megkülönböztethető egymástól, akkor létezik egy olyan hosszúságú kísérlet, amely meghatározza a kísérlet végének állapotát .${\ displaystyle (n; m; p)}$${\ displaystyle S}$${\ displaystyle {\ tfrac {n (n-1)} {2}}}$${\ displaystyle S}$

1957-ben AA Karatsuba bebizonyította a következő két tételt, amelyek teljesen megoldották Moore problémáját a 8. tétel kísérletének hossza javításával kapcsolatban.

A. tétel. Ha olyan gép, hogy minden két állapota megkülönböztethető egymástól, akkor legfeljebb egy elágazó hosszúságú kísérlet létezik , amelyen keresztül meghatározhatja a kísérlet végét.${\ displaystyle S}$${\ displaystyle (n; m; p)}$${\ displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$${\ displaystyle S}$

B tétel: Van egy gép, amelynek két állapota megkülönböztethető egymástól, oly módon, hogy a legrövidebb kísérletek hossza, amely megállapítja a gép állapotát a kísérlet végén, megegyezik .${\ displaystyle (n; m; p)}$${\ displaystyle {\ tfrac {(n-1) (n-2)} {2}} + 1}$

Az A és B tételeket egy negyedik hallgató, AA Karatsuba „A probléma az automaták elméletéből” című tanfolyamának alapjául használták, amelyet ajánlási referenciával különböztettek meg a Kar karának hallgatói munkáinak versenyén. mechanika és matematika a Moszkvai Lomonosowi Állami Egyetemen 1958-ban. Karatsuba dolgozatát az Uspekhi Mat folyóiratnak adták. Nauk 1958. december 17-én, és 1960 júniusában jelent meg ott.

A mai napig (2011) Karatsuba a kísérletek hosszára vonatkozó eredménye az egyetlen pontos nemlineáris eredmény, mind az automaták elméletében, mind a számítási komplexitáselmélet hasonló problémáiban.

Lásd még

• Szinkron áramkör
• Mealy gép
• Algoritmikus állapotgép
• Autonóm rendszer (matematika)

Hivatkozások

További irodalom

• Conway, JH (1971). Szabályos algebra és véges gépek . London: Chapman és Hall. ISBN 0-412-10620-5. Zbl  0231.94041 .
• Moore EF Gedanken-kísérletek szekvenciális gépeken. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, NJ (1956).
• Karatsuba AA Egy probléma megoldása a véges automaták elméletéből. Usp. Mat. Nauk, 15: 3, 157–159 (1960).
• Karatsuba AA Experimente mit Automaten (német) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).
• Karatsuba AA Kutatási munkák listája .

Moore-and-Mealy-Machine

Külső linkek

• Moore-géphez kapcsolódó média a Wikimedia Commons-ban