Ein Kellerautomat ist ein Endlicher Automat mit einem Stack (“Kellerspeicher”). Er wird mit PDA (pushdown automaton) bzw. NPDA (nondeterministic pushdown automaton) abgekürzt. Laut Wikipedia verwendet die Gleitkommaeinheit einen PDA. Dazu habe ich allerdings keine Quelle, das ist also mit Vorsicht zu genießen. Ein weiterer Einsatzzweck ist die Syntaxanalyse einer Tokenfolge. Das kann für Compiler oder [...]
Posts Tagged ‘Abstract machine’
Sprachen, Automaten und Grammatiken: Ein Überblick
January 28th, 2012
No Comments
Die folgende Tabelle gibt einen Überblick über formale Sprachen, die Automaten die sie akzeptieren und die Grammatiken, die sie erzeugen. Dabei haben die Grammatiken die Form : V: Die Menge der Nicht-Terminale. Für sie benutze ich Großbuchstaben. : Die Menge der Terminale. Für sie benutze ich Kleinbuchstaben. P: Die Produktion, also die Regeln mit denen [...]
Konstruktion eines deterministischen endlichen Automaten aus einem nicht-deterministischem
October 29th, 2011
2 Comments
Der nicht-deterministische endliche Automat zu dem regulärem Ausdruck ist folgender: Will man daraus nun den endlichen Automaten konstruieren, läuft das im Prinzip über eine Potenzmengenkonstruktion. Zuerst defnieren wir: Dann erstellen wir folgende Tabelle: {S} a b Dann überprüft man, welche Zustände erreicht werden können, wenn man vom jedem Zustand in der Startmenge (hier [...]
How to draw a finite-state machine
October 29th, 2011
2 Comments
Finite-state machines are necessary to show that some problems are computable (or not). As I am currently learning something about them, I would like to be able to plot those finite automatons automatically. I will use graphviz. Nondeterministic finite-state machine This image is created from a gv-file. I saved it as fsm.gv: To create a [...]
