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

De­ter­mi­nis­ti­sche end­li­che Au­to­ma­ten DEA (BP Items 1 ,7, 8, 11, 15)

Da Mealy-Au­to­ma­ten de­ter­mi­nis­tisch und (in der An­zahl ihrer Zu­stän­de) end­lich sind, sind sie de­ter­mi­nis­ti­sche end­li­che Au­to­ma­ten oder DEA. Meis­tens ist mit die­sem Be­griff9 al­ler­dings ein an­de­rer Typ Au­to­mat ge­meint, der keine Aus­ga­be, dafür aber so­ge­nann­te End­zu­stän­de hat. Die „Aus­ga­be“ eines sol­chen DFA be­steht nur darin, ob er am Ende der Ein­ga­be in einem sei­ner End­zu­stän­de ste­hen­bleibt oder in einem „nor­ma­len“. Falls er in einem End­zu­stand ste­hen­bleibt, sagt man „der Au­to­mat hat das Wort ak­zep­tiert“ – sonst hat er es nicht ak­zep­tiert.

Akzeptor für die Sprache der ungeraden Binärzahlen

Ab­bil­dung 2: Ak­zep­tor für die Spra­che der un­ge­ra­den Bi­n­är­zah­len ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Damit eig­nen sich DEAs be­son­ders dafür, ein Wort auf „Gül­tig­keit“, also auf Zu­ge­hö­rig­keit zu einer be­stimm­ten Spra­che zu prü­fen. Man nennt sie daher auch Ak­zep­to­ren oder er­ken­nen­de Au­to­ma­ten für eine Spra­che; in Ab­gren­zung dazu sind Mealy- und Moore-Au­to­ma­ten Trans­duk­to­ren, weil sie die Ein­ga­be in eine an­de­re Form über­füh­ren.

Genau wie ein Mealy-Au­to­mat hat der DEA in Ab­bil­dung 2 eben­falls Zu­stän­de (hier q0 und q1), einen Start­zu­stand (q0), ein Ein­ga­be­al­pha­bet (da es hier kein Ausgabe­alphabet gibt, schreibt man ∑ = {0, 1}) sowie Transi­tio­nen, die mit Alphabet­(Ein­ga­be-)zei­chen be­schrif­tet sind. Gegen­über den Mealy-Au­to­ma­ten kommt für die for­ma­le Be­schrei­bung eines DEA noch die Menge E ⊆ Q End­zu­stän­de hinzu, hier E={q1}.

End­zu­stän­de wer­den üb­li­cher­wei­se dop­pelt um­ran­det dar­ge­stellt wie hier q1.

Über­zeu­gen Sie sich, dass die­ser Au­to­mat genau dann in q1 steht, wenn un­mit­tel­bar vor­her eine 1 ge­le­sen wurde, sonst aber in q0. Falls die Ein­ga­be in die­sem Mo­ment endet, wird sie also „ak­zep­tiert“. Endet sie noch nicht, ar­bei­tet der DEA wei­ter. Ins­ge­samt ak­zep­tiert er alle Binär­zahlen, die auf 1 enden, z.B. 1, 1001, 1111, 000100101 – also genau die un­ge­ra­den. Ge­ra­de Binär­zahlen (die auf 0 enden) ak­zep­tiert er hin­ge­gen nie. Da er also genau10 die un­ge­ra­den ak­zep­tiert, ist er ein erkennen­der Au­to­mat für die Spra­che der un­ge­ra­den Bi­n­är­zah­len.

Erweiterung des obigen DFA.

Ab­bil­dung 3: Er­wei­te­rung des obi­gen DFA. Beim mit 1/0 dop­pelt be­schrif­te­ten Über­gang han­delt es sich genau ge­nom­men um zwei ein­zel­ne Über­gän­ge. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Ge­le­gent­lich haben Schü­ler die Fehl­vor­stel­lun­gen, dass aus einem End­zu­stand keine Tran­si­tio­nen mehr heraus­führen dürf­ten („da ist er doch schon fer­tig?“), oder dass DEA mit meh­re­ren End­zu­stän­den ir­gend­wie „mehr­deu­tig“ seien. Tat­säch­lich ist bei­des er­laubt und oft auch sinn­voll: es kommt nur dar­auf an, wo der DEA ge­ra­de steht, wenn die Ein­ga­be endet. Diese Fehl­vor­stel­lun­gen las­sen sich ver­mei­den, wenn im Un­ter­richt passen­de Bei­spie­le vor­kom­men, also DEA mit einem bzw. meh­re­ren End­zu­stän­den, Endzu­stän­de mit und ohne ab­ge­hen­de Tran­si­tio­nen.

Wel­che Wör­ter über {0,1} er­kennt der DEA in Ab­bil­dung 3?11

Schü­le­rin­nen müs­sen auch DEA so­wohl als Über­gangs­graph dar­stel­len, als auch for­mal kor­rekt be­schrei­ben kön­nen. Diese Be­schrei­bung um­fasst am Bei­spiel

  • das Ein­ga­be­al­pha­bet ∑ = {0, 1},
  • die Menge ℤ = {q0, q1, q2, q3, qF} der Zu­stän­de,
  • den Start­zu­stand s = q0
  • die Menge E der End­zu­stän­de, hier E={q3}
  • die Tran­si­ti­ons­ta­bel­le

Ein­ga­be →
alter Zust. ↓
0 1
q0 q0 q1

Be­mer­kung:
Wie bei Mealy-Au­to­ma­ten soll­te der Feh­ler­zu­stand qF im Über­gangs­gra­phen weg­ge­las­sen wer­den.

In der Ta­bel­le muss er nur auf­ge­führt wer­den, falls Transi­tionen aus einem „nor­ma­len“ Zu­stand dort­hin füh­ren; in die­sem Bei­spiel dürf­te er auch weg­ge­las­sen wer­den.

q1 q0 q2
q2 q0 q3
q3 q3 q3
qF qF qF

Am Über­gangs­gra­phen bzw. der Tran­si­ti­ons­ta­bel­le kann man auch nach­prü­fen, ob der Au­to­mat wirk­lich deter­ministisch ist: Dazu muss jede Tran­si­ti­on mit einem Al­pha­bet­zei­chen be­schrif­tet sein, darf also nur nach einer Ein­ga­be (aber nicht „spon­tan“) statt­finden. Zwei­tens darf es nie vor­kom­men, dass aus einem Zu­stand meh­re­re Über­gän­ge mit der glei­chen Ein­ga­be heraus­führen. Gäbe es von q2 aus meh­re­re Tran­si­tio­nen mit 1, „wüss­te“ der Auto­mat sonst nicht, wel­che davon er neh­men soll. Er müss­te so­zu­sa­gen „raten“; der Zu­fall darf bei de­ter­mi­nis­ti­schen Au­to­ma­ten aber keine Rolle spie­len.

Da ein DEA jedes Wort ent­we­der ak­zep­tiert oder nicht, legt er damit genau eine Spra­che fest, eben die Menge der ak­zep­tier­ten Wör­ter.

Las­sen Sie die Schü­ler dis­ku­tie­ren, ob auch die Um­keh­rung gilt: Legt jede Spra­che ihren akzeptie­ren­den Au­to­ma­ten ein­deu­tig fest? Tat­säch­lich ist das nicht der Fall: Es gibt zu jeder Spra­che viele Au­to­ma­ten, die diese Spra­che er­ken­nen.

DFA für eine didaktisch sehr stark vereinfache Erkennung von Mailadressen.

Ab­bil­dung 4: DFA für eine di­dak­tisch sehr stark ver­ein­fa­che Er­ken­nung von Mail­adres­sen. Zu­guns­ten der Les­bar­keit wer­den Buch­sta­ben hier durch ein „b“ und die im Dia­gramm schlecht er­kenn­ba­ren Punk­te durch „Punkt“ re­prä­sen­tiert. [CC BY-SA 4.0 DE], aus zpg_­spra­chen­au­to­ma­ten_hin­ter­grund.odt

Schon klei­ne DEAs kön­nen in­ter­es­san­te Auf­ga­ben lösen. Möch­te man bei­spiels­wei­se Mailadres­sen12 dar­auf prü­fen, ob sie

  • mit einem Be­nut­zer­na­men be­gin­nen (der eine Kom­bi­na­ti­on aus Buch­sta­ben und Punk­ten sein darf),
  • dann ein @ ent­hal­ten
  • und eine min­des­tens zwei­stu­fi­ge Domain­anga­be wie bbb.​b.​bb, wobei ein ein­zel­nes Zei­chen als Top­le­vel-Do­main nicht in Frage kommt
(so dass die Wör­ter b.​bbb@​bbbb, bb.​bb@​bb.​b, und bb.​bb@ also un­zu­läs­sig sind), dann kann ein DEA die­ses Pro­blem mit nur sie­ben Zu­stän­den und 13 Transi­tionen lösen; ein handgeschrie­be­nes Java-Pro­gramm für die glei­che Auf­ga­be wäre auf­wän­di­ger, un­über­sicht­li­cher, damit fehleran­fäl­liger und vor allem bei Än­de­run­gen viel schwie­riger anzupas­sen.

Wie wir auf Seite 3 ge­se­hen hat­ten, ist dabei die Er­ken­nung von Mail­adres­sen selbst in Li­bre­Of­fice noch etwas pri­mi­ti­ver als die­ser DEA.

Der Charme eines DEA ist, dass er an­hand der Über­gangs­ta­bel­le si­mu­liert wer­den kann, so­bald die voll­stän­di­ge Be­schrei­bung vor­liegt. Ein DEA für eine be­stimm­te Auf­ga­be (etwa Mailadres­sen) muss also gar nicht pro­gram­miert wer­den; statt­des­sen kann seine Übergangs­tabelle von einem DEA-Si­mu­la­tor be­nutzt wer­den, um den Mail­adres­sen- (oder jeden an­de­ren) DEA zu simu­lie­ren und mit be­lie­bi­gen Ein­ga­ben zu „füt­tern“. Diese Si­mu­la­ti­on kann in „Soft­ware und Pro­gram­mier­pro­jek­te“ (Seite 26) selbst pro­gram­miert wer­den.

Für der­ar­ti­ge Auf­ga­ben emp­fiehlt es sich, das Al­pha­bet wie hier ein­zu­schrän­ken, weil man dann nicht viele Pfei­le für alle 26 Buch­sta­ben zeich­nen muss, son­dern in­ter­es­san­te­re Fra­gen im Mit­tel­punkt ste­hen kön­nen.

Tat­säch­lich müs­sen in der Pra­xis letzt­lich weder DEA noch Über­gangs­ta­bel­le von Hand er­stellt wer­den: Sie las­sen sich aus einer tex­tu­el­len Be­schrei­bung (z.B. von gül­ti­gen Mail­adres­sen) auch au­to­ma­tisch er­zeu­gen, wenn die in Form so­ge­nann­ter re­gu­lä­rer Aus­drü­cke vor­liegt. Re­gu­lä­re Aus­drü­cke wer­den ab Seite 17 be­han­delt.

Gren­zen von DEAs

Al­ler­dings gibt es auch Dinge, die DEAs nicht kön­nen: Ob­wohl das Pro­blem nicht be­son­ders schwie­rig klingt, miss­lingt bei­spiels­wei­se schon der Ver­such, damit kor­rekt ge­klam­mer­te Re­chen­aus­drü­cke zu er­ken­nen: Aus­drü­cke, in denen alle ge­öff­ne­ten Klam­mern wie­der rich­tig ge­schlos­sen wer­den. Der Aus­druck ((2+a)*((3+x)*2)-1)/5 etwa ist kor­rekt ge­klam­mert, (2+5))*3( hin­ge­gen nicht.

DEAs kön­nen sol­che Klam­mer­spra­chen je­doch nicht er­ken­nen: Um den kor­rek­ten Ab­schluss der Klam­me­rung zu prü­fen, müss­te der Au­to­mat sich wäh­rend der Ver­ar­bei­tung des Wor­tes ja „mer­ken“, wie viele Klam­mern ge­ra­de offen sind (in wel­cher Klam­me­rungs­tie­fe er sich also be­fin­det). Einem DEA ste­hen als „Ge­dächt­nis“ aber nur seine Zu­stän­de zur Ver­fü­gung. Ein Au­to­mat mit drei Zu­stän­den kann also höchs­tens drei Klam­me­rungs­ebe­nen un­ter­schei­den und schei­tert spä­tes­tens an der vier­ten; da jeder DEA eine end­li­che und vor allem feste An­zahl von Zu­stän­den hat, ist prin­zi­pi­ell kein DEA in der Lage, be­lie­big tief ge­schach­tel­te Klammer­aus­drücke zu über­prü­fen.

Da die Ana­ly­se der­ar­ti­ger re­kur­siv ge­schach­tel­ter Struk­tu­ren aber häu­fig vor­kommt, braucht man dafür ein mäch­ti­ge­res Au­to­ma­ten­mo­dell, und zwar die so­ge­nann­ten Kel­ler­au­to­ma­ten13, die nicht nur Zu­stän­de, son­dern zu­sätz­lich einen Kel­ler­spei­cher (Stack) un­be­grenz­ter Ka­pa­zi­tät haben. Sie wer­den ab Seite 11 be­spro­chen.

 

9 Auch im Deut­schen wird oft das eng­li­sche DFA für „de­ter­mi­nis­tic fi­ni­te au­to­ma­ton“ be­nutzt.

10 Be­to­nun­gen wer­den in die­sem Skript durch kur­si­ve Schrift an­ge­deu­tet.

11 Die­ser Au­to­mat er­kennt nicht mehr die­sel­be Spra­che wie der vo­ri­ge: Außer den un­ge­ra­den Bi­n­är­zah­len er­kennt er auch Wör­ter, die „111“ ent­hal­ten. Diese Zif­fern­fol­ge führt ihn näm­lich in den End­zu­stand q3, den er dann nicht mehr ver­lässt.

12 Mail­adres­sen eig­nen sich gut als Bei­spiel für den Un­ter­richt, weil sie (2020 noch) allen Schü­lern ge­läu­fig sind. In Wirk­lich­keit ist die Prü­fung von Mail­adres­sen noch viel kom­pli­zier­ter, weil viele Son­der­fäl­le zu be­ach­ten sind; in Pro­gram­mier­erfo­ren wird aus­drück­lich davor ge­warnt, Mail­adres­sen mit selbst ge­strick­tem Code prü­fen zu wol­len. Nach Norm (RFC 2822) sind im User­na­men näm­lich nicht nur + oder Leer­zei­chen er­laubt, son­dern sogar das @ – es muss al­ler­dings mit einem Back­slash „mas­kiert“ wer­den. Sehr viele, auch große Mail­an­bie­ter wei­gern sich aber, sol­che (nach RFC zu­läs­si­gen!) Kon­ten an­zu­le­gen. Viel­leicht haben sie Be­den­ken, die Gül­tig­keits­prü­fung sonst nicht rich­tig hin­zu­be­kom­men...

13 Statt Kel­ler sagt man oft auch „Sta­pel“ oder „Stack“.

 

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

 

Wei­ter zu Nicht­de­ter­mi­nis­ti­sche end­li­che Au­to­ma­ten NEAs