FH Graubünden PH Graubünden

Endliche Automaten

Algorithmisches Denken in der Primarschule

Zusammenfassung

In der Informatik geht es zu einem wesentlichen Teil um das Finden von Mustern in Daten bzw. darum, Daten nach einem gewissen Muster zu erzeugen. In dieser Unterrichtseinheit betrachten wir strukturierte Texte («Lieder»), die nach einem festen Regelsystem aufgebaut sind. Die erzeugenden Mechanismen (wir sprechen hier von «Diagrammen») sind hier sogenannte Endliche Automaten, die eine andere Darstellungsform für reguläre Ausdrücke sind. Diese erlauben es, Regeln darzustellen, die festlegen, wie Buchstaben (oder hier Teile von «Liedern») aneinander gereiht werden dürfen, um Texte (hier «Lieder») zu erzeugen.

Reguläre Ausdrücke bzw. endliche Automaten spielen eine sehr wichtige Rolle in der Textverarbeitung und der Formalisierung von Programmiersprachen, also Sprachen, die der Computer «verstehen» kann. Dazu wird vorgegeben, welche Wörter auf bestimmte Wörter folgenden dürfen oder welche Teile eines Textes wiederholt werden dürfen. Endliche Automaten eignen sich sehr gut, um diese Regeln übersichtlich darzustellen.

In dieser Unterrichtseinheit werden unterschiedliche Automaten vorgestellt, um Lieder zu beschreiben. Es finden sich diverse Aufgabentypen, die eine einfache Differenzierung ermöglichen.

Beispielsequenz

Lisa singt gerne Lieder – aber nicht beliebige Lieder, sondern nur Lisa-Lieblings-Lieder. Alle ihre Lieblings-Lieder sind nach einem festen System aufgebaut und gehen beispielsweise so:

Dum-da-da Dum-da-da Bimmelim Dum-da-da Dum-da-da

oder auch

Dum-da-da Dum-da-da Bimmelim Dum-da-da Dum-da-da Bimmelim
Dum-da-da Dum-da-da Bimmelim Dum-da-da Dum-da-da

Lisa-Lieblings-Lieder bestehen also aus der Wiederholung von «Dum-da-da Dum-da-da», wobei immer ein «Bimmelim» zwischen zwei Wiederholungen kommt. Um sich das merken zu können, erstellt Lisa folgendes Diagramm: .automat01.jpg. Um zu singen, beginnt Lisa bei «Start» und folgt dann den Pfeilen, um die Abfolge der Worte richtig zu singen. Das Lied beenden darf sie nur, wenn sie auf «Ende» kommt.

Nach einer Zeit wird ihr langweilig und sie möchte statt der Wiederholung von «Dum-da-da» auch noch «Wupp-di-du lalala» singen können. Um beides zu kombinieren erstellt sie das folgende Diagramm: .automat02.jpg. Wieder beginnt sie bei «Start» und endet bei «Ende».

Wupp-di-du lalala Wupp-di-du lalala
Dum-da-da Dum-da-da Bimmelim Dum-da-da Dum-da-da

oder auch

Dum-da-da Dum-da-da Bimmelim Wupp-di-du lalala Wupp-di-du lalala
Dum-da-da Dum-da-da Bimmelim Wupp-di-du lalala
Dum-da-da Dum-da-da Bimmelim Dum-da-da Dum-da-da

Lisa möchte neue Lieder singen, die mit Diagrammen dargestellt werden. Hier und da sind ihr bei der Konstruktion der Diagramme leider Fehler passiert. Können Sie ihr helfen, diese in den folgenden Aufgaben zu korrigieren?

Aufgabe 1

Betrachten Sie das folgende Diagramm. .automat03.jpg. Welches der folgenden Lieder kann mit dem Diagramm nicht gesungen werden?

  1. Lala Dada Diddel-di Dada Dum Dada Dum Dada-dam
  2. Dum-di Dum Dada Dada-dam
  3. Dum-di Dum Dada Dum Lalala Dada Diddel-di Dada Dum Dada-dam

Aufgabe 2

Die drei folgenden Diagramme sollen für das gleiche Lied erstellt worden sein, aber leider ist ein erneuter Fehler passiert. Welches ist für ein anderes Lied, das heisst, welches Diagramm passt nicht zu den anderen?


  1. .automat04.jpg.

  2. .automat05.jpg.

  3. .automat06.jpg.

Aufgabe 3

Betrachten Sie das folgende Diagramm und die Lieder, die mit diesem gesungen werden können. .automat07.jpg. Lisa hat festgestellt, dass sie für dieselben Lieder unterschiedliche Diagramme erstellen kann. Im Folgenden sehen Sie drei Vorschläge, welche alle für dasselbe Lied sein sollen. Allerdings ist nur eines der drei korrekt.

Welches Diagramm erlaubt es, dieselben Lieder zu singen wie das am Anfang dargestellte?


  1. .automat08.jpg.

  2. .automat09.jpg.

  3. .automat10.jpg.

Lösungen zu den Aufgaben

Aufgabe 1

Das zweite Lied kann nicht gesungen werden, da auf das «Dada» kein «Dada-dam» folgen kann.

Aufgabe 2

Das erste und das dritte Diagramm sind für dieselben Lieder. Hier ist der wesentliche Punkt, dass auf ein «La La» immer ein «Wupp-di-duu» oder am Ende ein «Badum» folgen muss. Insbesondere kann «La La Wupp-di-duu» beliebig oft wiederholt werden, was mit dem zweiten Diagramm nicht möglich ist. Eine besondere Schwierigkeit ist hier, dass der Start bei den letzten beiden Diagrammen auf der rechten Seite liegt. Dies ist Absicht, da es die Einsicht bringen soll, dass dies für die erzeugten Lieder nicht relevant ist. Die Regeln sagen, dass man beim Start beginnen und den Pfeilen folgen soll; die relativen Positionen enthalten keine Information. Somit kann auch «dasselbe» Diagramm auf viele unterschiedliche Weisen gezeichnet werden.

Aufgabe 3

Das dritte Diagramm ist für dieselben Lieder. Der wesentliche Punkt ist, dass mit dem Mittelteil das «Dup-pi» jeweils eine ungerade Anzahl oft wiederholt werden kann.

Um dies besser zu verstehen, nummerieren wir die Kreise durch: .automat11.jpg. Um ein

Jup-pi Dup-pi Duu

zu singen, gehen wir vom Start zur 2 und dann zum Ende. Für ein

Jup-pi Dup-pi Dup-pi Dup-pi Duu

haben wir zwei Möglichkeiten. Zunächst können wir vom Start zur 1, dann zur 2 und dann zum Ende. Alternativ können wir aber auch vom Start zur 2, dann zur 3, dann zurück zur 2 und dann zum Ende. Wollen wir nun weitere

Dup-pi Dup-pi

einfügen, so kann dies erreicht werden, indem zwischen 3 und 2 die entsprechende Anzahl Male hinundher gelaufen wird.

Didaktischer Kommentar

Mit dem Computer zu arbeiten, bedeutet im Wesentlichen Informationen zu verarbeiten. Damit dies geschehen kann, müssen die Informationen aber zunächst dargestellt werden. Hierbei geht es insbesondere darum, Muster zu identifizieren, um eine potenziell unendlich grosse Menge an Informationen endlich codieren zu können. Bei der Darstellung von Texten («Liedern») mit endlichen Automaten («Diagrammen») haben wir es mit einer solchen endlichen Darstellung für potenziell unendlich viele Texte zu tun. Sie kommen in der Praxis in allen möglichen Anwendungen vor, oftmals in Form der eingangs erwähnten regulären Ausdrücke, welche eine andere Darstellungsform für obige Diagramme sind.

Diese Unterrichtseinheit enthält die folgenden Aspekte des algorithmischen Denkens.

Quellenangaben und weiterführende Literatur

Diese Unterrichtseinheit wurde in abgeänderter Form für den Informatik-Biberwettbewerb eingereicht. Alle Inhalte stehen unter Creative-Commons-Lizenz.

Wie bereits erwähnt sind reguläre Ausdrücke bzw. endliche Automaten ein wichtiges Thema in der Informatik. Die Literatur ist reichhaltig, eine zu tiefe Auseinandersetzung mit der Thematik allerdings zur Verwendung dieser Unterrichtseinheit nicht notwendig.

Interessant ist das Gebiet der Formalen Sprachen vor allem, da nicht nur eine Brücke auf der Ebene Primarstufe bzw. Sekundarstufe I zwischen Sprache und Informatik gebaut werden kann, sondern dies auch für die Linguistik und die Informatik auf Hochschulniveau gilt.

  1. Hans-Joachim Böckenhauer und Juraj Hromkovič: Formale Sprachen. Endliche Automaten, Grammatiken, lexikalische und syntaktische Analsyse. Springer Vieweg, 2012.
  2. Reguläre Ausdrücke: Wikipedia – Die freie Enzyklopädie. https://de.wikipedia.org/wiki/Regulärer_Ausdruck, 02.10.2021.

Abbildungsverzeichnis

Alle Abbildungen wurden durch den Autor erzeugt.

Zurück PDF Übungen als PDF