Unterscheid DEA und NEA

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  muss für jedes Zeichen des Eingabealphabets  ein Übergang in einen Folgezustand existieren.[1] 
Unterschiede

 Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.

 Er unterscheidet sich darin von nichtdeterministischen endlichen Automaten, deren Zustandswechsel sich nicht immer deterministisch ereignen müssen.

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

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