Recent Posts

Kellerautomat

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 gefunden, das ist also mit Vorsicht zu genießen. Ein weiterer Einsatzzweck ist die Syntaxanalyse einer … Read More »

Sprachen, Automaten und Grammatiken: Ein Überblick

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 $G = (V, \Sigma, P, S)$: V: Die Menge der Nicht-Terminale. Für sie benutze ich Großbuchstaben. $\Sigma$: Die Menge der Terminale. Für sie benutze ich … Read More »

Konstruktion eines deterministischen endlichen Automaten aus einem nicht-deterministischem

Der nicht-deterministische endliche Automat zu dem regulärem Ausdruck $(a \cup (ab(b)^\text{}ba))^\text{}$ ist folgender: $Q = {S, q_1, q_2}$ $\Sigma = {a, b}$ $\delta = \text{siehe Grafik}$ $F = {S}$ $NEA = \left( Q, \Sigma, \delta, S, F \right)$ Nondeterministic finite-state machine Will man daraus nun den endlichen Automaten konstruieren, läuft … Read More »

How to draw a finite-state machine

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 Nondeterministic finite-state machine This image is created from a gv-file … Read More »