Automaten
(immerhin stammen einige der tiefergehenden Artikel über Automaten auf Wikipedia von mir).
Die Klasse ist z.Z. aber Work-In-Progress.
Selbstverständlich habe ich auch eine Klasse für
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 solch ein Automat mit einem Keller-Alphabet auskommt, das nur 1 Element hat, kann man den Keller durch
ein einzelnes Zählregister ersetzen.
Dann hat man die folgende Register-Maschine:
Ein JavaScript, das Conways Game of Life
(einen weiteren zellulären Automaten)
auf einer HTML5 Canvas simuliert.
Interessanterweise ist das System Turing-Vollständig, obwohl es auf den ersten Blick überhaupt nicht danach aussieht. Hier sind ein paar Videos 1 2 3 die das illustrieren.
Interessanterweise ist das System Turing-Vollständig, obwohl es auf den ersten Blick überhaupt nicht danach aussieht. Hier sind ein paar Videos 1 2 3 die das illustrieren.
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
Binärzahlen erkennt, die durch 3 teilbar sind.
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).
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).
Ü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
Übersetzt Klartext in
Morsecode und
Morsecode in Klartext.
Formal handelt es sich dabei um
Moore- oder
Mealy-Automaten.
Hier ist auch eine Version in C++.
Hier ist auch eine Version in C++.
23 KiB
Ein Programm, das (basierend auf dem Algorithmus string_search)
die Bereiche zwischen einem gegebenen 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 HTML-Dateien 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. Dass der Automat trotzdem minimal ist, lässt sich leicht dadurch beweisen, dass alle Präfixe des gesuchten Strings in verschiedenen Myhill-Nerode Äquivalenzklassen liegen.
Wie ich inzwischen erfahren habe, ist das der Knuth-Morris-Pratt-Algorithmus.
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. Dass der Automat trotzdem minimal ist, lässt sich leicht dadurch beweisen, dass alle Präfixe des gesuchten Strings in verschiedenen Myhill-Nerode Äquivalenzklassen liegen.
Wie ich inzwischen erfahren habe, ist das der Knuth-Morris-Pratt-Algorithmus.