Scribd Logo
Hochladen

Willkommen bei Scribd!

  • 33 Ansichten

    ε NFA

    Hochgeladen von

    Chivu Adlerauge

    Copyright:

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

    ε NFA

    Hochgeladen von

    Chivu Adlerauge
    33 Ansichten2 Seiten

    Originaltitel

    ε-NFA

    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?

    Copyright:

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

    ε NFA

    Hochgeladen von

    Chivu Adlerauge

    Copyright:

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

    Definition – Nichtdeterministischer endlicher Automat mit ε-Übergängen

    Ein nichtdeterministischer endlicher Automat mit ε-Übergängen


    (non-deterministic finite automaton with ε-moves 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 ×Σ∪ {ε}) → 2Q
    (2Q 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

    ∩ Schnittmenge
    ∪ Vereinigung

    Vorteile eines ε-NFA:


    • Manche Sprachen deutlich einfacher modellieren
    • Reguläre Sprachen besser zeigen

    Definition – ε-Hülle
    Die ε-Hülle (ε-closure), kurz ECLOSE wird induktiv definiert.
    Induktionsbeginn: ECLOSE(q) = q
    Induktionsschritt: Wenn Zustand p in ECLOSE(q) ist und es einen
    Übergang δ(p, ε) = p′ gibt, dann ist auch p′ in ECLOSE(q).
    Die ε-Hülle einer Zustandsmenge S ⊆ Q ist wie folgt definiert:
    ECLOSE(S) = ∪q∈SECLOSE(q).
    Zusammenfassung: ECLOSE(q) sind nur die Zustände, die nur mit ε
    erreichbar sind

    Definition – Erweiterte Übergangsfunktion für ε-NFA


    Die erweiterte Übergangsfunktion (extended transition function) ˆδ für
    einen ε-NFA wird definiert als:
    Induktionsbeginn: ˆδ(q, ε) = ECLOSE(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) = ECLOSE(δ(p1, a))∪ECLOSE(δ(p2, a))∪· · ·∪ECLOSE(δ(pk,
    a)).
    nach meiner Verständnise ist die Reihenflolge ist: Tabelle
    ablesen - ECLOSE - Vereinigen alle ECLOSE
    Zusammenfassung: Immer beachten auch ε mit
    Übergangsfunktion auslösen

    Definition – Vom ε-NFA akzeptierte Sprache


    Sei E = (Q, Σ, δ, q0, F) ein ε-NFA. Die vom ε-NFA E akzeptierte
    Sprache L(E) (language L(E) is accepted by the ε-NFA E) ist
    definiert als:
    L(E) = { w ∈ Σ∗ | ˆδ(q0, w) ∩ F ̸= ∅ }.
    D.h. w ist in L(E), wenn ˆδ(q0, w) mindestens einen
    Endzustand enthält.

    Verfahren – ε-NFA → DFA


    Sei E = (QE, Σ, δE, q0, FE) ein ε-NFA.
    Dann kann der äquivalente DFA D = (QD, Σ, δD, qD, FD) wie folgt
    definiert werden:
    • QD ist die Menge aller (erreichbaren) durch ε-Hülle
    abgeschlossenen Teilmengen von QE
    • Anfangszustand qD ist ECLOSE(q0)
    • FD sind die Teilmengen von Zuständen mit mindestens einem
    akzeptierenden Zustand aus FE
    • δD für alle a ∈ Σ und S = {p1, . . . , pk} ∈ QD sei definiert
    durch: δD(S, a) = ∪ki=1ECLOSE(δE(pi, a)).

    Theorem Eine Sprache L wird durch einen DFA akzeptiert genau dann, wenn L
    durch einen ε-NFA akzeptiert wird.
    Beweis-Skizze:
    • DFA ⇐ ε-NFA: zum DFA per Verfahren umwandeln, danach
    vollständige Induktion über die Länge der Wörter
    • DFA ⇒ ε-NFA: füge dazu in DFA nur noch zusätzliche Transitionen
    δ(q, ε) = ∅ für alle q ∈ Q ein

    Das könnte Ihnen auch gefallen