Grammatiken und Automaten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

Registriere dich um viele Vorteile zu genießen! Weniger Werbung, bessere Kommunikation und vieles mehr!

  • Jede Programmiersprache hat ihre Grammatiken diese Drückt man durch Automaten aus.
    Dieser Eintrag soll euch die Funktionsweise von Automaten näherbringen und was für Grammatiken es gibt.
    1. Endliche Automaten
    1.1. Grundeigenschaften:
    Eigenschaften die jeder Endliche Automat hat sind Z.B. einen Startzustand und mind. einen Endzustand(akzeptierter Zustand)
    jeder Automat hat eine von ihm verstandene Sprache, und kann in einem Tupel wieder gegeben werden. (A = (Q, Σ, δ, q0, F))
    [Q = Zustände, Σ Zeichen die Verstanden werden, δ übergebe Funktion, q0 Startzustand(muss nicht q0 sein), F Akzeptierte Zustände]

    jeder Endlicher Automat hat einen Regulären Ausdruck

    Bsp:
    Spoiler anzeigen
    Tupel: A = ({q0,q1,q2,q3,q4},{0,1},δ,q0,{q3,q4})
    L(A)=(∃w∈{0,1}*|u,x∈{0,1}*.w=u1x)
    (0+1)*1(0+1)*


    1.2. Deterministische Endliche Automaten (DEA)

    Bsp. anhand von Zeichnung.
    Besonderheit: ein Dea hat genau eine Möglichkeit der Zustandsänderung je Zeichen

    .
    1.3. Nichtdeterministische Automaten (NEA)

    Besonderheiten: für jedes Zeichen gibt es beliebig viel mögliche Zustandsänderungen (nur Gültig wenn es einen Pfad zum Endzustand gibt der nicht ins leere Verläuft. gibt N^X möglichkeiten (N anzahl der verstanden Zeichen, X schritt anzahl.)

    1.3.1 ε-Nea
    ist eine Form vom Nea mit ε-Übergängen. (ε = {ε}= leeres Wort)(|ε|=0)

    1.4. Teil-Mengen-Konstruktion
    für jeden NEA existiert ein dazugehöriger DEA.
    die Teilmengen Konstruktion ist eine Möglichkeit der Umwandlung in dem man für jeden Schritt die Möglichen Schritte aufschreibt.
    Bsp. am Bild:

    Spoiler anzeigen


    01
    q0q01q0start Zustand

    q01q01q02
    q02q01q0*(Endzustand)






    und so haben wir jetzt einen Dea zu dem Nea gefunden mit 3 Automaten das Tupel sieht so aus: A=(P({q0,q1,q2}),{0,1},δ,q0,P({q0,q1,q2})/{q0,q1})=({q0,q01,q02},{0,1},δ,q0,{q02})

    2. Grammatiken
    2.1.Allgemeines:
    Jede Programmier Sprache hat ihren Aufbau(Grammatik) und besteht aus Automaten

    man Teilt Sprachen in bestimmte Typen ein je welche Grammatik sie haben.

    2.2 Grammatiken:
    Spoiler anzeigen

    • kontextsensitiv: Regeln x A y→x z y oder S→ǫ
    • expansiv: Regeln x→z mit |x|≤|z|, oder S→ǫ
    • kontextfrei: Regeln A→z
    • linear: Regeln A→ǫ oder A→u B v
    • rechtslinear: Regeln A→ǫ oder A→a B
    • linkslinear: Regeln A→ǫ oder A→B a


    oben stehen die Regeln je nach dem wie eine Sprache definiert ist gilt die Einteilung.

    2.2.1 Aufbau
    jede Sprache wird mit Terminalwörtern gebildet. Z.B.: haben wir die Bildungsregel: R --> 0R0|0R|S1; S--> 1T1; 1T1 --> 101U; U --> 0|1 dies wäre eine kontextsensitiv Grammatik
    Spoiler anzeigen
    Beispiel:
    R-->0R-->00R0-->00S10-->001T110-->00101U10-->00101110




    2.3 Typen von Sprache:
    zu jeder Grammatik gibt es eine Sprache diese werden in Typen aufgeteilt. hier eine Kleine Übersicht:
    Spoiler anzeigen

    allgemein (Typ 0): keine Einschränkung an die Produktionen
    • kontextsensitiv (Typ 1)– nur Regeln der Form x A y→x z y oder S→ǫ (x, y, z ∈ Γ∗, A ∈ V, z 6=ǫ)
    (S→ǫ nur erlaubt, wenn S nicht rechts in einer anderen Regel auftaucht, Γ = V ∪T)
    • expansiv– nur Regeln der Form x→z mit |x|≤|z|, oder S→ǫ (x, z ∈ Γ+)
    (S→ǫ nur erlaubt, wenn S nicht rechts in einer anderen Regel auftaucht)
    • kontextfrei (Typ 2)– nur Regeln der Form A→z (z ∈ Γ∗, A ∈ V )
    • linear– nur Regeln der Form A→ǫ oder A→u B v (A, B ∈ V, u, v ∈ T∗)
    • rechtslinear (Typ 3)– nur Regeln der Form A→ǫ oder A→a B (A, B ∈ V, a ∈T)
    Manche Bücher: nur Regeln der Form A→ǫ oder A→v B (A, B ∈V, v ∈T∗)
    • linkslinear– nur Regeln der Form A→ǫ oder A→B a (A, B ∈ V, a ∈T)

    jeder Type ist Teil der Sprache des niederen Types bsp.: ist Type 3 eine Teilmenge der Sprache von Type 2 die Wiederum von Type 1 und die Wiederum von Type 0.

    ich hoffe ich konnte euch die Theorie der Informatik ein bisschen näher bringen.

    211 mal gelesen

Kommentare 4

  • Janhektor -

    Ich schließe mich @Aquaatic an.
    Zudem enthält der Artikel mehrere zum Teil gravierende Fehler.
    "jeder Automat hat einen Regulären Ausdruck" -- das ist schlicht falsch. Gegenbeispiel: Kellerautomaten. Sehr elementarer Fehler.
    "ε = {}= leeres Wort" -- das leere Wort ist gerade nicht identisch mit der leeren Menge, ein beliebter Fehler beim Einsteigern.
    "für jeden NEA existiert ein dazugehöriger DEA" -- unpräzise. Beschreibt lediglich irgendeine beliebige Abbildung. Entscheidend ist, dass der DEA äquivalent zum NEA ist. Ansonsten ist dieser Satz unbedeutend und trivial.
    "Programmier Sprache hat ihren Aufbau(Grammatik) und besteht aus Automaten" -- Viel Spaß mit Programmiersprachen, die nicht mächtiger als reguläre Ausdrücke sind...

    Tut mir leid, aber dem Eintrag lassen sich wenige positive Aspekte abgewinnen, was schade ist.
    Trotzdem ist es schön, dass du dir die Mühe dazu gemacht hast, das Lexikon ein Stück zu erweitern.

    • Letsplaybar -

      oh hatte das endliche bei den Automaten vergessen, und mit dem leeren Wort stimmt da muss das ε rein in die Klammern grade auch aufgefallen
      Zu dem 3. Punkt nein da man den DEA optimieren kann ist es möglich ein DEA zu entwerfen der die selben Wörter akzeptiert wie der NEA aber nicht alle Zustandsmöglichkeiten Abdeckt, und damit nicht äquivalent sein muss die Aussage sagt auch nur aus das eine existiert nicht wie viel existieren. die zugehörigen DEA's zum NEA haben die selbe Sprache, aber nicht das selbe Tupel und sind daher zwar von der Sprache äquivalent aber von den Zuständen nicht(nicht alle). es gibt bei einem NEA Zustände die ins leere verlaufen diese muss man bei einem DEA nicht mit angeben, kann dies aber. Deine Aussage würde auf den unoptimierten zutreffen.
      Jeder reguläre Ausdruck hat eine Bildungsregel/Sprache, mit Hilfe von dieser kann man eine Grammatik bestimmen. (sind wir grade in der UNI dabei)
      Werde sobald ich mehr Zeit habe (nächste Woche den Beitrag erweitern mit Beweisen, und genauerem Inhalt)

  • Aquaatic -

    Viel zu wenig erklärt. Außerdem sind die Informationen sehr unübersichtlich dargestellt. Du solltest zudem auf Rechtschreibung und Grammatik achten.

    • Letsplaybar -

      zur Erklärung wird es noch Nachträge geben, die ausführlicher sind. hatte bloß grade nicht so viel Zeit und da man es nicht zwischen Speichern kann... und die Übersichtlichkeit lässt sich nur beschränkt beeinflussen werde noch versuchen es besser zu formatieren