Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:automaten:lepro:erstellung2:start [23.09.2020 17:33] – [Los gehts...] sbel | faecher:informatik:oberstufe:automaten:lepro:erstellung2:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Automaten Entwerfen II - formale Sprachen ====== | ||
- | ===== Übersicht ===== | ||
- | |||
- | Automaten werden z. B. als Grundlage für Compiler verwendet. Ein Compiler soll erkennen, ob die Syntax der in den Computer eingegebenen Codes richtig ist. Der zugrundeliegende Automat muss also gewährleisten, | ||
- | " | ||
- | |||
- | ===== Lernziel ===== | ||
- | |||
- | Nach diesem Kapitel kannst du ... | ||
- | * endliche Automaten als Graphen darstellen. | ||
- | * natürliche und formale Sprachen unterscheiden und außerdem Begriffe einer formalen Sprache wie z. B. Sprache des Automaten oder Wort verwenden. | ||
- | * Sprachen von Automaten beschreiben. | ||
- | * zu einer gegebenen Sprache einen Automaten konstruieren. | ||
- | |||
- | |||
- | ====== Los gehts... ====== | ||
- | |||
- | Du hast bis jetzt viele verschiedene Automaten kennengelernt. Außerdem hast du im letzten Kapitel | ||
- | gelernt, wie man Automaten verändert und damit auch das Akzeptanzverhalten des Automaten beeinflusst. Auf diesem Wissen baust du nun auf, denn jetzt konstruierst du deinen Automaten von Grund | ||
- | auf selber! Lies dazu zunächst noch ein Beispiel durch: | ||
- | |||
- | Es soll ein Automat konstruiert werden, der eine vierstellige Zahl übergeben bekommt. Der Automat | ||
- | soll diese Zahl akzeptieren, | ||
- | diesem Automaten außerdem ausschließlich vierstellige Zahlen übergeben; so muss zum Beispiel für | ||
- | die Zahl 100 die vierstellige Zahl 0100 eingegeben werden. Die vorderen Nullen haben dabei keinerlei | ||
- | Bedeutung. | ||
- | |||
- | Wie muss aber ein Automat aussehen, der nur gerade Zahlen akzeptiert? | ||
- | Natürlich ist bei dieser Frage nur die letzte Ziffer der Zahl interessant, | ||
- | ablesen, ob eine Zahl gerade ist, oder nicht. Die ersten drei Ziffern der Zahl sind also für den Automaten uninteressant. Das lässt sich folgendermaßen darstellen: | ||
- | |||
- | {{ : | ||
- | |||
- | Dieser Automat " | ||
- | |||
- | |||
- | Ist die letzte Ziffer eine 1, 3, 5, 7 oder 9 – ist die Zahl also ungerade – soll der Automat die Zahl verwerfen. Diese Unterscheidung zwischen geraden und ungeraden Zahlen lässt sich folgendermaßen umsetzen: | ||
- | |||
- | {{ : | ||
- | {{ : | ||
- | |||
- | |||
- | |||
- | |||