Scribd Logo
Hochladen

Willkommen bei Scribd!

  • 20 Ansichten

    NFA

    Hochgeladen von

    Chivu Adlerauge
    Das Dokument erklärt die Definitionen und Konzepte von nichtdeterministischen endlichen Automaten (NFA). Es beschreibt die grundlegenden Bestandteile eines NFA wie Zustände, Übergangsfunktion und akzeptierte Sprache. Weiterhin wird die Teilmengenkonstruktion erläutert, mit der ein äquivalenter deterministischer endlicher Automat (DFA) aus einem NFA erzeugt werden kann.

    Copyright:

    © All Rights Reserved
    Als TXT, PDF, TXT herunterladen oder online auf Scribd lesen

    NFA

    Hochgeladen von

    Chivu Adlerauge
    20 Ansichten2 Seiten
    Das Dokument erklärt die Definitionen und Konzepte von nichtdeterministischen endlichen Automaten (NFA). Es beschreibt die grundlegenden Bestandteile eines NFA wie Zustände, Übergangsfunktion und akzeptierte Sprache. Weiterhin wird die Teilmengenkonstruktion erläutert, mit der ein äquivalenter deterministischer endlicher Automat (DFA) aus einem NFA erzeugt werden kann.

    Copyright

    © © All Rights Reserved

    Verfügbare Formate

    TXT, PDF, TXT oder online auf Scribd lesen

    Stufen Sie dieses Dokument als nützlich ein?

    Sind diese Inhalte unangemessen?

    Das Dokument erklärt die Definitionen und Konzepte von nichtdeterministischen endlichen Automaten (NFA). Es beschreibt die grundlegenden Bestandteile eines NFA wie Zustände, Übergangsfunktion und akzeptierte Sprache. Weiterhin wird die Teilmengenkonstruktion erläutert, mit der ein äquivalenter deterministischer endlicher Automat (DFA) aus einem NFA erzeugt werden kann.

    Copyright:

    © All Rights Reserved
    Als TXT, PDF, TXT herunterladen oder online auf Scribd lesen
    Als txt, pdf oder txt herunterladen
    20 Ansichten2 Seiten

    NFA

    Hochgeladen von

    Chivu Adlerauge
    Das Dokument erklärt die Definitionen und Konzepte von nichtdeterministischen endlichen Automaten (NFA). Es beschreibt die grundlegenden Bestandteile eines NFA wie Zustände, Übergangsfunktion und akzeptierte Sprache. Weiterhin wird die Teilmengenkonstruktion erläutert, mit der ein äquivalenter deterministischer endlicher Automat (DFA) aus einem NFA erzeugt werden kann.

    Copyright:

    © All Rights Reserved
    Als TXT, PDF, TXT herunterladen oder online auf Scribd lesen
    Als txt, pdf oder txt herunterladen
    von 2

    L = { w | w endet mit 01 }

    q0 hat mehrere Ausgänge für 0


    q1 hat einen Ausgang für 1, aber keinen für 0, d.h. 0 schlägt fehl
    q2 hat keine Ausgänge, d.h. q2 akzeptiert keine weiteren Eingaben
    Vorteil: NFA ist oft intuitiver zu entwickeln

    Definition – Nichtdeterministischer endlicher Automat


    Ein nichtdeterministischer endlicher Automat (non-deterministic finite
    automaton or NFA)
    ist ein 5-Tupel A = (Q, Σ, δ, q0, F) mit
    • Q: endliche Menge von Zuständen (states)
    • Σ: ein Alphabet
    • δ: eine Übergangsfunktion (transition function) mit δ : (Q × Σ) → 2^Q
    (2^Q ist die Menge aller Teilmengen von Q)
    • q0 : der Startzustand (start state) aus Q
    • F: Menge der Endzustände (final states or accept states) mit F⊆Q

    Definition – Erweiterte Übergangsfunktion für NFA


    Die erweiterte Übergangsfunktion (extended transition function) ˆδ für einen
    NFA wird definiert als:
    Induktionsbeginn: ˆδ(q, ε) = {q}.
    Induktionsschritt: Sei w = xa, d.h. a ist das letzte Zeichen des Wortes
    w ∈ Σ∗
    und gelte ˆδ(q, x) = {p1, p2, . . . , pk}.
    Dann gilt: δˆ(q, w) = δ(ˆδ(q, x), a) = δ(p1, a) ∪ δ(p2, a) ∪ · · · ∪
    δ(pk, a).

    Hinweis bei DFA :Wenn laut die Sprache Null akzeptiert


    bedeutet nicht dass Ziffern 0 akzeptiert sondern leeres Wort akzeptiert.

    Definition – Vom NFA akzeptierte Sprache


    A = (Q, Σ, δ, q0, F)
    vom NFA A akzeptierte Sprache L(A)ist definiert als:
    L(A) = { w ∈ Σ∗ | ˆδ(q0, w) ∩ F ̸= ∅ }.
    D.h. w ist in L(A), wenn ˆδ(q0, w) mindestens einen
    Endzustand enthält.

    Verfahren – NFA → DFA mit Teilmengenkonstruktion (subset construction)


    Konstruiere DFA D aus NFA N = (QN, Σ, δN, q0, FN) wie folgt:
    DFA D = (QD, Σ, δD, {q0}, FD)
    QD Menge aller Teilmengen von QN
    FD Menge aller Teilmengen S von QN mit S ∩ FN ̸= ∅.
    nur die einem Endzustand enthält (S ist Selektion)
    Für jedes S ⊆ QN und a ∈ Σ gilt:
    δD(S, a) = ∪p∈SδN(p, a)
    Die geschweifte Klammer sind hier keine Mengen
    sondern Namen der Zuständen von neuen DFA

    Verfahren NFA → DFA abwartende Auswertung(lazy evaluation)


    Induktionsanfang: {q0} ist erreichbar.
    Induktionsschritt:
    Zustand S ∈ DFA mit S ⊆ QN erreichbar
    dann alle a ∈ Σ die Zustände δD(S, a) erreichbar.

    Theorem – Äquivalenz NFA–DFA durch Teilmengenkonstruktion


    DFA D = (QD, Σ, δD, {q0}, FD) der zu gegebenem
    NFA N = (QN, Σ, δN, q0, FN)
    durch die Teilmengenkonstruktion generiert
    wurde, dann gilt L(D) = L(N).
    Beweis-Skizze: durch vollständige Induktion über die Länge
    der Wörter

    Eine Sprache L wird durch einen DFA akzeptiert genau dann, wenn L durch einen
    NFA akzeptiert wird.
    DFA ⇐ NFA: Theorem NFA → DFA
    DFA ⇒ NFA: klar, da jeder DFA auch ein NFA ist

    Textsuche ist eine praktische Anwendung von endlichen Automaten


    Verfahren – Konstruktion NFA zur Textsuche
    Automat
    k + 1 Zustände:
    q0 den Startzustand
    weitere Zustände q1, . . . , qk,
    folgende Übergänge
    δ(q0, a) = q0 für a ∈ Σ und
    δ(qi−1, ai) = qi für i = 1, . . . , k.
    Der Endzustand sei qk.
    Für mehrere Worte füge entsprechende weitere Zustände ein.

    Das könnte Ihnen auch gefallen