← Informatik · Q3 · Thema 3.2
Wie liest ein Barcodescanner einen Strichcode, und warum kann ein endlicher Automat keine Klammern zählen? Von Zuständen und Übergängen über Grammatiken und den Kellerautomaten bis zur Turingmaschine. Hier gibt es das Skript zum Nachlesen, eine Simulation zum Minimieren und FLACI zum Ausprobieren im Browser.
Moore & MealyDEAMinimieren
NEAGrammatikenChomsky-Hierarchie
KellerautomatTuringmaschine
Inhalt des Skripts
- 1Endliche Automaten: Moore und MealyS. 3
- 2Der DEA: Definition, Barcodescanner, StrichbreitenS. 6
- 2.4Akzeptoren und ihre SpracheS. 9
- 3Einen DEA minimierenS. 10
- 4.2Nichtdeterministische Automaten (NEA)S. 11
- 4.3Vom NEA zum DEA: die TeilmengenkonstruktionS. 11
- 4.5Grenzen endlicher AutomatenS. 13
- 5Grammatiken und Chomsky-HierarchieS. 14
- 5.3Vom Automaten zur regulären GrammatikS. 15
- 6KellerautomatenS. 17
- 7Die TuringmaschineS. 19
- 7.5Was die Turingmaschine bedeutetS. 21
- 8Überblick: Welches Modell kann was?S. 22
- 9–10Übungen mit LösungenS. 23
Simulation: einen DEA minimieren
Das Tabellenverfahren aus Abschnitt 3 Schritt für Schritt – mit Dreiecksmatrix, Begründung für jedes Paar und dem fertigen Minimalautomaten. Eigene Automaten lassen sich eintippen.
⤢ Im Vollbild öffnenWelches Modell kann was?
| Modell | Speicher | Sprachklasse | Beispiel |
|---|---|---|---|
| DEA / NEA | keiner (nur der Zustand) | regulär (Typ 3) | endet auf ab; Anzahl b durch 3 teilbar |
| Kellerautomat | Keller | kontextfrei (Typ 2) | aⁿbⁿ, Klammerterme, Palindrome |
| linear beschränkte Turingmaschine | Band so lang wie die Eingabe | kontextsensitiv (Typ 1) | aⁿbⁿcⁿ |
| Turingmaschine | unendliches Band | rekursiv aufzählbar (Typ 0) | alles Berechenbare |