Logo
Unionpedia
Kommunikation
Jetzt bei Google Play
Neu! Laden Sie Unionpedia auf Ihrem Android™-Gerät herunter!
Installieren
Schneller Zugriff als Browser!
 

Deterministischer endlicher Automat

Index Deterministischer endlicher Automat

Ein deterministischer endlicher Automat (DEA; 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.

20 Beziehungen: Äquivalenzrelation, Chomsky-Hierarchie, Eindeutiger endlicher Automat, Endlicher Automat, Formale Grammatik, Jeffrey Ullman, John E. Hopcroft, Kurt-Ulrich Witt, Nerode-Relation, Nichtdeterminismus, Nichtdeterministischer endlicher Automat, Potenzautomat, Potenzmengenkonstruktion, Rajeev Motwani, Reguläre Sprache, Regulärer Ausdruck, Tupel, Uwe Schöning, Wort (Theoretische Informatik), Zweiwege-DFA.

Äquivalenzrelation

Unter einer Äquivalenzrelation versteht man in der Mathematik eine Relation, die reflexiv, symmetrisch und transitiv ist.

Neu!!: Deterministischer endlicher Automat und Äquivalenzrelation · Mehr sehen »

Chomsky-Hierarchie

Chomsky-Hierarchie, gelegentlich Chomsky-Schützenberger-Hierarchie (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger), ist ein Begriff aus der Theoretischen Informatik.

Neu!!: Deterministischer endlicher Automat und Chomsky-Hierarchie · Mehr sehen »

Eindeutiger endlicher Automat

Der eindeutige endliche Automat (UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl. DFA) und dem nichtdeterministischen endlichen Automaten (NEA, engl. NFA) ein.

Neu!!: Deterministischer endlicher Automat und Eindeutiger endlicher Automat · Mehr sehen »

Endlicher Automat

Abb. 1: Beispiel eines EA, der eine Tür beschreibt Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat;, FSM) ist ein Modell eines Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen.

Neu!!: Deterministischer endlicher Automat und Endlicher Automat · Mehr sehen »

Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die mit Hilfe des Semi-Thue-Systems angegeben werden und durch die formale Sprachen beschrieben und erzeugt werden können.

Neu!!: Deterministischer endlicher Automat und Formale Grammatik · Mehr sehen »

Jeffrey Ullman

Jeffrey David Ullman (* 22. November 1942 in New York City) ist ein US-amerikanischer Informatiker.

Neu!!: Deterministischer endlicher Automat und Jeffrey Ullman · Mehr sehen »

John E. Hopcroft

John E. Hopcroft, 2009 John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker.

Neu!!: Deterministischer endlicher Automat und John E. Hopcroft · Mehr sehen »

Kurt-Ulrich Witt

Kurt-Ulrich Witt (* 1953) ist ein deutscher Mathematiker und theoretischer Informatiker.

Neu!!: Deterministischer endlicher Automat und Kurt-Ulrich Witt · Mehr sehen »

Nerode-Relation

Die Nerode-Relation (auch: Nerode-Kongruenz oder Nerode-Rechtskongruenz) ist eine Äquivalenzrelation auf den Präfixen einer formalen Sprache, die in der Theoretischen Informatik untersucht wird.

Neu!!: Deterministischer endlicher Automat und Nerode-Relation · Mehr sehen »

Nichtdeterminismus

Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt.

Neu!!: Deterministischer endlicher Automat und Nichtdeterminismus · Mehr sehen »

Nichtdeterministischer endlicher Automat

Grafische Darstellung eines NEA Ein nichtdeterministischer endlicher Automat (NEA;, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt.

Neu!!: Deterministischer endlicher Automat und Nichtdeterministischer endlicher Automat · Mehr sehen »

Potenzautomat

Ein Potenzautomat ist ein Begriff der theoretischen Informatik.

Neu!!: Deterministischer endlicher Automat und Potenzautomat · Mehr sehen »

Potenzmengenkonstruktion

Die Potenzmengenkonstruktion (Myhill-Konstruktion oder auch Teilmengenkonstruktion) ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt.

Neu!!: Deterministischer endlicher Automat und Potenzmengenkonstruktion · Mehr sehen »

Rajeev Motwani

Rajeev Motwani 2006 Rajeev Motwani (* 26. März 1962 in Jammu; † 5. Juni 2009 in Atherton) war ein indischer Informatiker.

Neu!!: Deterministischer endlicher Automat und Rajeev Motwani · Mehr sehen »

Reguläre Sprache

In der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge eine formale Sprache, die einigen Einschränkungen unterliegt.

Neu!!: Deterministischer endlicher Automat und Reguläre Sprache · Mehr sehen »

Regulärer Ausdruck

Ein regulärer Ausdruck (Abkürzung RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient.

Neu!!: Deterministischer endlicher Automat und Regulärer Ausdruck · Mehr sehen »

Tupel

Tupel (abgetrennt von mittellat. quintuplus ‚fünffach‘, septuplus ‚siebenfach‘, centuplus ‚hundertfach‘ etc.) sind in der Mathematik neben Mengen eine wichtige Art und Weise, mathematische Objekte zusammenzufassen.

Neu!!: Deterministischer endlicher Automat und Tupel · Mehr sehen »

Uwe Schöning

Uwe Schöning (* 28. Dezember 1955 in Ulm) ist ein deutscher Informatiker.

Neu!!: Deterministischer endlicher Automat und Uwe Schöning · Mehr sehen »

Wort (Theoretische Informatik)

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets.

Neu!!: Deterministischer endlicher Automat und Wort (Theoretische Informatik) · Mehr sehen »

Zweiwege-DFA

In der Informatik ist ein Zweiwege deterministischer endlicher Automat (Zweiwege-DFA, 2DFA) ein Automat, genauer gesagt ein deterministischer endlicher Automat (DFA), der bereits gelesene Zeichen noch einmal besuchen kann.

Neu!!: Deterministischer endlicher Automat und Zweiwege-DFA · Mehr sehen »

Leitet hier um:

Deterministische Maschine.

AusgehendeEingehende
Hallo! Wir sind auf Facebook! »