Informatik-Blog

Formal definiert man einen nichtdeterministischen endlichen Automat als 5-Tupel (Q, s,  ∑, F,  δ): - Q ist einen nicht leere, endliche Menge von Zuständen - S  ∈ Q ist der Startzustand -  ∑ ist ein nicht leeres endliches Eingabealphabet - F ist die Menge der akzeptiert en  Endzustände, wobei F eine Teilmenge von Q ist -  Δ: Q x  ∑ -> Q^n ist die Übergangsrelation, die jeder Kombination aus einem Zustand und einem Eingabezeichen mindestens einen Nachfolgezustand zuordnet.

Ein Automat wird als endlich bezeichnet, weil die Mengen der Eingaben, der Ausgaben und Zustände, die sie durchlaufen, endlich sind. Ein Automat ist eine endliche, nicht leere Menge Σ. Die Elemente eines Alphabets können alle möglichen Symbole sein (Ziffern, Zeichen ...). Ein in der Informatik oft gebrauchtes Alphabet ist Σ bool={0, a}. Die Buchstaben eines Alphabets sein frei wählbar. Formal definiert man einen Mealy-Automat als 6-Tupel (Q, s, Σ,  Ω,  δ,  λ) : - Q ist eine nicht leere, endliche Menge von Zuständen - s ∈ Q ist der Startzustand - Σ ist ein nicht leeres, endliches Eingabealphabet -  Ω ist ein nicht leeres, endliches Ausgabealphabet -  δ : Q x   Σ  -> Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet. -   λ : Q x Σ ->  Ω ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet. ...

Formal definiert man einen deterministischen endlichen Automaten als 5-Tupel (Q, s, Σ, F, σ): - Q ist eine nicht leere, endliche Menge von Zuständen - s ∈ Q ist der Startzustand -  Σ ist eine nicht leeres, endliches Eingabealphabet - F ist die Menge der akzeptierten Endzustände, wobei F eine Teilmenge von Q ist - σ Q x Σ -> Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet. Ein Fehlerzustand (Fehlersenke) ist ein Zustand, von dem man nicht mehr in einen akzeptierten Endzustand gelangen kann. Die Menge der Wörter, die vom Automaten akzeptiert werden, also die Wörter, bei denen der Automat in einen akzeptierten Endzustand gelangt, nennt man die vom Automaten akzeptierte Sprache. Ein Automat heißt deterministisch, wenn für jeden seiner Zustände und für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. Ein Wort über dem Alp...

Eine Liste ist eine lineare Datenstruktur, die beliebig viele Objekte verwalten kann. Das Einfügen und Löschen von Elementen ist an jeder Position möglich. Die hier verwendete Variante der Liste nennt man auch einfach verkettete Liste. Man kann jedoch auch andere Modellierungen wählen, indem z.B. jeder Knoten mit seinem Nachfolger und Vorgänger verknüpf wird. Man spricht dann von einer doppelt verketteten Liste. Diese Variante kann das Auffinden eines Elementes in der Liste beschleunigen. Einige wichtige Methoden der LinkedList, sind folgende: public boolean isEmpty ( ) public E get ( int index ) public boolean add ( E e ) public boolean removeLast ( ) public boolean removeFirst ( ) Beispiel: // LinkedList wird erzeugt LinkedList list = new LinkedList ( ) ; // Hinzufügen von Objekten list. add ( new Punkt ( ) ) ; list. add ( new Punkt ( ) ) ; // Entfernen des ersten Objektes list. removeFirst ( ) ;

Mehrdimensionale Arrays In Java kann man aber auch mehrdimensionale Arrays erstellen. Bei diesen handelt es sich um ineinander geschachtelte Arrays: Die Elemente der ersten Dimension sind Arrays, die selber wieder Arrays der zweiten Dimension enthalten usw. Jede Dimension wird durch ein Paar eckiger Klammern dargestellt.  In einem zweidimensionalen Array lassen sich zum Beispiel Daten aus einer Tabelle ablegen. Das erste Klammernpaar könnte dann z.B. für die Zeile, das zweite für die Spalte stehen. Beispiel: double [ ] [ ] tabelle = new double [ 20 ] [ 10 ] ; /* Tabelle mit Elementen vom Typ double mit 20 Zeilen und 10 Spalten */ Wertsetzung: tabelle [ 11 ] [ 3 ] = 2.74 ;     Bei der Objekt-Erzeugung eines mehrdimensionalen Arrays muss mindestens die Größe der ersten Dimension bekannt sein. Das Attribut length gibt immer die Größe der aktuellen Dimension an. Wenn sie ein Element auf unterster Ebene ansprechen wollen, dann müssen di...

Eindimensionale Arrays Eindimensionale Arrays (deutsch: Felder) sind im Prinzip einfache Listen. Diese Arrays werden mit einem Datentypen deklariert, d.h. alle Werte, die in diesem Array gespeichert werden sollen, müssen von demselben Datentyp sein, mit dem das Array deklariert wurde. Das Array ist nur so lang, wie es definiert wurde. Es besitzt ein festgelegtes Attribut (lenght), welches nicht überschritten werden kann. Sonst kommt es zur java.lang.ArrayIndexOutOfBoundsException . Deklaration: Datentyp [ ] Arrayname = new Datentyp [ Länge ] ; /* Syntax für die Deklaration eines Arrays */ Datentyp Arrayname [ ] = new Datentyp [ Länge ] ; /* Syntax für die Deklaration eines Arrays */ Um ein bestimmtes Element des Arrays ansprechen zu können, hat jedes Element eine Nummer, den sogenannten Index. Das erste Element bekommt den Index 0, das zweite den Index 1 usw.  Mit folgender Syntax weist man einem Element des Arrays einen Wert zu: Arrayname [ Inde...