www.AlgorithMan.de
where theory comes alive
Automaten
Selbstverständlich habe ich auch eine Klasse für Automaten (immerhin stammen einige der tiefergehenden Artikel über Automaten auf Wikipedia von mir). Die Klasse ist z.Z. aber Work-In-Progress.
2 KiB
Ein Javascript, das Langtons Ameise (einen zellulären Automaten) auf einer HTML5 Canvas simuliert.
65 KiB
Ein extrem kleines Programm (ohne Kommentare hat der Quellcode nur 370 Bytes, die kompilierte Binary 8,3 KiB), das prüft, ob ein gegebener String ein wohlgeformter arithmetischer Ausdruck ist. Das Programm entspricht einem Kellerautomaten für die Kontextfreie Grammatik
S ---> ( S ) | S+S | S-S | S*S | S/S | Num
Num ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Num Num
Da der Automat mit einem Keller-Alphabet auskommt, das nur 1 Element hat, kann man den Keller durch ein einzelnes Zählregister ersetzen. Dann hat man den folgenden Automaten: arith_check
5 KiB
Ein Javascript, das Conways Game of Life (einen weiteren zellulären Automaten) auf einer HTML5 Canvas simuliert.
19 KiB
Ein Programm, das zu zwei Zahlen n und b einen Automaten konstruiert, der Zahlen im b-adischen Zahlensystem erkennt, die durch n teilbar sind. So, wie zum Beispiel dieser Automat coset_dfa Binärzahlen erkennt, die durch 3 teilbar sind.
513 KiB
Generiert aus Dateien einen (bzgl. zeichenweiser Kodierung) optimalen Codebaum mit der Huffman-Kodierung. Formal ist ein Codebaum ein Moore- oder Mealy-Automat.
Unsere Seminar-Ausarbeitung und Vortrags-Folien vom Proseminar Datenkompression, WS 2004/05 am Lehrstuhl i6 sind auch enthalten (auf aktuellen LaTeX compilern lassen sich die Folien nicht mehr ganz richtig kompilieren).
3 KiB
Übersetzt Zahlen in ihre (deutsche) Sprechweise. Z. B. erzeugt es für die Zahl 12345 die Ausgabe
zwölf tausend drei hundert fünf und vierzig
14 KiB
Zwei Programme, die Klartext in Morsecode bzw. Morsecode in Klartext übersetzen. Formal handelt es sich dabei um Moore- oder Mealy-Automaten.
23 KiB
Ein Programm, das (basierend auf dem Algorithmus string_search) die Bereiche zwischen einem start-string und einem end-string aus stdin extrahiert und auf stdout ausgibt. Damit kann man z.B. so
cat foo.html | ./string_extract 'href="' '"'
die Ziele von Hyperlinks aus einer html-Datei extrahieren.
22 KiB
Ein Programm, das prüft, ob ein String in einem anderen vorkommt. Dazu baut es einen minimalen deterministischen Automaten für den gesuchten String.

Das interessante daran ist, dass die Konstruktion des deterministischen Automaten nicht über die Minimierung der Potenzmengen-Konstruktion nach Thompson-Konstruktion realisiert ist, sondern der Automat direkt aus dem String konstruiert wird, wofür lediglich eine Laufzeit von \(O(n^2)\) benötigt wird, entgegen der Potenzmengen-Konstruktion, die \(O^*(2^n)\) benötigt (wobei n die Länge des gesuchten Strings ist). Dass der Automat trotzdem minimal ist, lässt sich leicht dadurch beweisen, dass alle Präfixe des gesuchten Wortes in verschiedenen Myhill-Nerode Äquivalenzklassen liegen.

Wie ich inzwischen erfahren habe, ist das der Knuth-Morris-Pratt-Algorithmus.