Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Mealy-Au­to­ma­ten (neu im BP: Item 7)

Die so­ge­nann­ten Mealy-Au­to­ma­ten gel­ten als be­son­ders an­schau­lich: Sie kön­nen in jedem Schritt außer der Än­de­rung des in­ter­nen Zu­stands auch eine Aus­ga­be er­zeu­gen4 und er­lau­ben damit die Mo­del­lie­rung z.B. von Ge­trän­ke-, Fahr­kar­ten- oder ähn­li­chen Au­to­ma­ten, was für den Un­ter­richt eine sprach­li­che Par­al­le­le zwi­schen Au­to­ma­ten des All­tags und der Au­to­ma­ten­theo­rie er­laubt.

Mealy-Getränkeautomat

Ab­bil­dung 1: Mealy-Ge­trän­ke­au­to­mat, der Cola, Ap­fel­saft bzw. nicht ver­brauch­tes Gut­ha­ben aus­gibt. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Als Bei­spiel5 soll ein Ge­trän­ke­au­to­mat die­nen, der die Tas­ten A, C und S hat (für Ap­fel­saft, Cola und Stop) und Mün­zen à €1 und €2 an­nimmt, so dass die Menge der „Zei­chen“ {C, A, S, 1, 2} sein Al­pha­bet, also die mög­li­chen Ein­ga­ben dar­stellt. Die Ab­bil­dung zeigt einen sol­chen Automa­ten in Form eines an­schau­li­chen (Zu­stands-)Über­gangs­gra­phen6. Der Au­to­mat befin­det sich immer in genau einem der run­den Zu­stän­de; an­fangs ist es für Schü­ler hilf­reich, ihn als Spiel­plan an­zu­se­hen, auf dem man „mit einer Spiel­fi­gur Züge macht“. Der Au­to­mat be­ginnt immer im Start­zu­stand, der mit einem zu­sätz­li­chen Pfeil (hier Drei­eck) „von links“ mar­kiert wird. Jede Ein­ga­be be­wirkt einen „Zug“ (Über­gang oder Tran­si­ti­on ge­nannt, dar­ge­stellt durch einen Pfeil zu einem an­de­ren Zu­stand) und bei Mealy-Au­to­ma­ten auch eine Aus­ga­be.

Der Über­gang „C; Colaf­la­sche“ wird bei­spiels­wei­se durch­lau­fen, wenn der Au­to­mat im Zu­stand q1 ist und dort die Ein­ga­be „C“ er­hält; dabei gibt er eine Colaf­la­sche aus und wech­selt in den Zu­stand q0.

Der obige Graph ist al­ler­dings un­voll­stän­dig: Auch im Zu­stand q2 könn­te der Kunde ja die a-Taste drü­cken, aber der Graph zeigt nicht, was der Au­to­mat dann tun soll. Per Kon­ven­ti­on gibt es daher in jedem Über­gangs­gra­phen einen wei­te­ren, un­sicht­ba­ren „Feh­ler“zu­stand, zu dem grund­sätzlich alle „feh­len­den“ Tran­si­tio­nen hin­füh­ren; zu­guns­ten der Über­sicht wer­den aber weder der Feh­ler­zu­stand, noch die Über­gan­ge dort­hin ein­ge­zeich­net. Eine wei­te­re Kon­ven­ti­on be­sagt, dass der Au­to­mat aus dem Feh­ler­zu­stand nie (durch keine Ein­ga­be) wie­der heraus­kommt.

Oft wird im Un­ter­richt und auch in Klau­su­ren wegen der An­schau­lich­keit nur der Übergangs­graph ver­wen­det. Zu einer for­mal kor­rek­ten, voll­stän­di­gen, ins­be­son­de­re maschinen­lesbaren Be­schrei­bung7 des Au­to­ma­ten ge­hö­ren aber wei­te­re An­ga­ben:

… all­ge­mein: … im Bei­spiel:
das Ein­ga­be­al­pha­bet ∑E ∑E = {S, C, A, 1, 2} des­sen Ele­men­te hier für die „Knöp­fe“ Stop, Cola, Ap­fel­saft bzw. den Ein­wurf von Mün­zen à €1 und €2 ste­hen.
eine Menge ℚ von Zu­stän­den ℚ ={q0, q1, q2}
der Start­zu­stand s = q0
das Aus­ga­be­al­pha­bet ∑A ∑A =
{Ap­fel­saft­fla­sche, Colaf­la­sche,
€1 Rück­geld, €2 Rück­geld,
„Gut­ha­ben €1“, „Gut­ha­ben €2“}

sowie eine Funk­ti­on für Über­gän­ge und eine für die Aus­ga­ben, die je­weils als Ta­bel­le oder als Graph an­ge­ge­ben wer­den kön­nen:

Über­gangs­funk­ti­on δ: ℚ⊗ ∑E → ℚ
Ein­ga­be →
alter Zust. ↓		 s a c 1 2
q0 q0 qF qF q2 q1
q1 q0 q0 q0 qF qF
q2 q0 qF qF q1 qF
qF qF qF qF qF qF
Aus­ga­be­funk­ti­on λ: ℚ⊗ ∑E → ∑A
Ein­ga­be →
alter Zust. ↓		 s a c 1 2
q0 - - - „Gut­ha­ben €1“ “Gut­ha­ben €2“
q1 €2 Rück­geld Ap­fel­saft­fla­sche Colaf­la­sche - -
q2 €1 Rück­geld - - “Gut­ha­ben €2“ -
qF - - - - -

Die Dar­stel­lun­gen könn­ten ver­ein­facht auch in einer ein­zi­gen Ta­bel­le zu­sam­men­ge­fasst wer­den, die dann in der glei­chen Zelle je­weils den neuen Zu­stand und die Aus­ga­be ver­eint.

Vor allem die Ta­bel­len er­for­dern im Un­ter­richt eine ge­naue Er­klä­rung und etwas Übung8 : Die eine Achse ist mit den Zu­stän­den, die an­de­re mit den Zei­chen des Eingabe­alpha­bets be­schrif­tet. Für jede Kom­bi­na­ti­on aus altem Zu­stand und Ein­ga­be ent­hält die Ta­bel­le den neuen Zu­stand bzw. (bei Mealy-Au­to­ma­ten) die Aus­ga­be, die beim Zustands­übergang er­fol­gen soll.

Auch wenn man im Gra­phen auf den Feh­ler­zu­stand qF und die Transi­tio­nen dort­hin ver­zich­tet, soll­te qF bei der Dar­stel­lung als Ta­bel­le be­rück­sich­tigt wer­den: Damit wird näm­lich deut­lich, dass der Über­gangs­graph eher für einen mensch­li­chen Be­trach­ter ge­dacht ist, der sich qF „hin­zu­denkt“ und von einem über­sicht­li­che­ren Dia­gramm pro­fi­tiert; die Ta­bel­le hin­ge­gen soll einer Maschi­ne die voll­au­to­ma­ti­sche Si­mu­la­ti­on des DEA er­lau­ben und muss dafür voll­ständig sein.

Die vier­te Zeile der Über­gangs­ta­bel­le sorgt dafür, dass der Au­to­mat den Feh­ler­zu­stand nicht wie­der ver­las­sen kann. Die­ses Ver­hal­ten ist für einen rea­len Ge­trän­ke­au­to­ma­ten na­tür­lich nicht er­wünscht, für eine ein­fa­che Mo­del­lie­rung aber oft vor­teil­haft.

Di­dak­ti­scher Tipp: Wich­ti­ge Grund­vor­stel­lun­gen für alle Typen von Au­to­ma­ten

Ob der Un­ter­richts­gang nun mit Mealy- oder an­de­ren Au­to­ma­ten be­ginnt – in jedem Fall soll­ten die Schü­ler beim Um­gang mit Au­to­ma­ten vor allem fol­gen­de Grund­vor­stel­lun­gen ent­wi­ckeln:

  1. Au­to­ma­ten be­ste­hen aus dis­kre­ten Zu­stän­den.
  2. Auch die Ein­ga­be be­steht aus dis­kre­ten Zei­chen (oder „Er­eig­nis­sen“) eines fes­ten Al­pha­bets.
  3. Die Ein­ga­be „steu­ert“ den Au­to­ma­ten zwi­schen den Zu­stän­den.
  4. Ähn­lich wie ein Pro­gramm be­nö­tigt der Au­to­mat weder In­tui­ti­on noch Über­blick: Er „weiß“ nicht, wel­che Ein­ga­ben spä­ter noch fol­gen, und auch nicht, wie der Graph ins­ge­samt aus­sieht, son­dern trifft alle Ent­schei­dun­gen lokal, so­fort und nach ein­fa­chen Re­geln.
  5. Der Ab­lauf wird nicht vom Zu­fall be­ein­flusst, son­dern ist voll­kom­men de­ter­mi­nis­tisch.
  6. Das in der In­for­ma­tik all­ge­gen­wär­ti­ge EVA-(Ein­ga­be-Ver­ar­bei­tung-Aus­ga­be)-Prin­zip ist bei Au­to­ma­ten be­son­ders klar und of­fen­sicht­lich. Es bie­tet sich an, es bei die­ser Ge­le­gen­heit noch­mals zu be­spre­chen (bzw. ein­zu­füh­ren).

 

4 Bei einem wei­te­ren Typ, den so­ge­nann­ten Moore-Au­to­ma­ten, steht die Aus­ga­be nicht an den Tran­si­tio­nen, son­dern in den Zu­stän­den. Moore-Au­to­ma­ten pro­du­zie­ren also beim Er­rei­chen eines be­stimm­ten Zu­stands immer die glei­che, zu die­sem Zu­stand ge­hö­ri­ge Aus­ga­be (und nicht beim Durch­lau­fen einer be­stimm­ten Tran­si­ti­on).

5 Die Au­to­ma­ten in die­sem Do­ku­ment wur­den mit der sehr emp­feh­lens­wer­ten Soft­ware JFLAP (https://​www.​jflap.​org/​jf­lapt­mp/) kon­stru­iert. Sie er­laubt nicht nur das Zeich­nen des Gra­phen, son­dern auch die Si­mu­la­ti­on des Au­to­ma­ten mit vor­ge­ge­be­nen Ein­ga­ben und kann sogar zwi­schen ver­schie­de­nen äqui­va­len­ten Dar­stel­lun­gen um­wan­deln, etwa einen Au­to­ma­ten in eine Gram­ma­tik, einen re­gu­lä­ren Aus­druck um­wan­deln usw. Eine eben­falls emp­feh­lens­wer­te Al­ter­na­ti­ve dazu ist der „Ex­or­ciser“ (https://​www.​swis­se­duc.​ch/​in­for­ma­tik/​ex­or­ciser/).

6 Die Be­zeich­nun­gen Über­gangs- oder Tran­si­ti­ons­dia­gramm sind eben­falls üb­lich.

7 Diese Be­schrei­bung wird im schrift­li­chen Ab­itur auch ver­langt.

8 Um­wand­lun­gen von Graph zu Ta­bel­le und um­ge­kehrt sind Stan­dard­auf­ga­ben im schrift­li­chen Ab­itur.

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][669 KB]

 

Wei­ter zu De­ter­mi­nis­ti­sche end­li­che Au­to­ma­ten DEA