NEA-Automat

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 akzeptierten 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.

Kommentare

Kommentar veröffentlichen

Beliebte Posts aus diesem Blog

Formale Sprachen

  Unter Synatx versteht man allgemein ein Regelsystem zur Kombination elementarer Zeichen zu zusammengesetzten Zeichen in natürlichen oder künstlichen Zeichensystemen. Die Syntaxregeln der Grammatik der deutschen Sprache geben, z.B. an, in welcher Reihenfolge die Satzglieder (elementar) in einem Satz (zusammengesetzt) angeordnet werden dürfen. Eine formale Sprache L über einem Alphabet ∑ ist eine Teilmenge aller möglichen Verknüpfungen des Alphabets. Neben der Bezeichnung Nicht-Terminal (N) wird auch häufig der Begriff Variable (V) verwendet. Ebenso wird die Menge der Terminale auch mit ∑ angegeben, da die Terminale die Symbole des Alphabets der Sprache sind. Die Grammatik der lal-Sprache wird formal wie folgt dargestellt: G lal = (N, T, S, P) Die Grammatik ist eine 4-Tupel N = {S, A, B} Die Nichtterminale sind Platzhalter für die Erzeugung von Worten. S steht als Platzhalter für die erste, A für die zwei...
Mehr anzeigen

Unterscheid DEA und NEA

Bild
Ein  nichtdeterministischer endlicher Automat  ( NEA ;  englisch   nondeterministic finite automaton ,  NFA ) ist ein  endlicher Automat , bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt.  Ein  deterministischer endlicher Automat  ( DEA ;  englisch   deterministic finite state machine  oder  deterministic finite automaton ,  DFA ) ist ein  endlicher Automat , der unter Eingabe eines Zeichens seines Eingabealphabetes (den möglichen Eingaben) von einem Zustand, in dem er sich befindet, in einen eindeutig bestimmten Folgezustand wechselt. Von jedem (Final-)Zustand  {\displaystyle q_{n}\in \{F,Q\}}  muss für jedes Zeichen des Eingabealphabets  {\displaystyle \Sigma }  ein Übergang in einen Folgezustand existieren. [1]   Unterschiede Im Unterschied zum  deterministischen endlichen Automaten  sind die Möglichkeiten nicht eindeutig, dem Automaten ist...
Mehr anzeigen

Beispiel Stack und Queue

/**  * Das Programm soll eine bestimmte Zahlenfolge aus einer Queue auslagern  * und in einem Stack ablegen - und zwar in umgekehrter Reihnfolge. */ package trhekegmu; import java.util.Deque; import java.util.LinkedList; /**  *  * @author, GK Q1  * @date 14.03.2018  *  */ public class Trhekegmu {         private static final Deque<Integer> queue = new LinkedList<>();     /**      * @param args the command line arguments      */     public static void main(String[] args) {                 addNumber(10);         addNumber(4);         addNumber(6);         addNumber(8);         addNumber(1);         addNu...
Mehr anzeigen