TU Wien:Formale Modellierung VU (Salzer)/Kapitel Formale Sprachen und Grammatiken

From VoWi
Jump to navigation Jump to search

Reguläre Sprachen[edit]

Operationen auf formalen Sprachen[edit]

Seien zwei Sprachen.

Vereinigung
Verkettung
Potenzen
Kleene-Stern

Definition regulärer Sprachen[edit]

Reguläre Sprachen sind alle Sprachen, die aus einem Alphabet mit Hilfe von Vereinigung, Verkettung und Stern gebildet werden können.

Reguläre Ausdrücke[edit]

  • algebraische Notation
Operatorrangfolge (absteigend): *, +
  • EBNF-Notation
  • Syntaxdiagramme
Reg. Sprache Algebra EBNF Syntaxdiagramm
Abkürzung

─>A─>

Leersprache
Leerwortsprache
───────>
Terminalsymbol "s" ─>s─>
Aufeinanderfolge ─> X ─> Y ─>
Alternativen
 ╭─> X ─╮
─┤      ├─>
 ╰─> Y ─╯
Option
 ╭─────╮
 │     v
─┴─ X ───>
Wiederholung ≥ 0
 ╭─ X <─╮
 v      │
────────┴─>
Wiederholung ≥ 1
 ╭──────╮
 v      │
─── X ──┴─>
Gruppierung
  • Posix Extended Regular Expressions (ERE)

Eigenschaften regulärer Sprachen[edit]

Nicht regulär sind Sprachen, deren Analyse ein unbegrenztes Gedächtnis erfordert.

Vom regulären Ausdruck zum Automaten[edit]

Vom Automaten zum regulären Ausdruck[edit]

Verallgemeinerter endlicher Automat

  • keine Übergänge in den Anfangszustand
  • nur ein Endzustand, der nicht Anfangszustand ist
  • keine Übergänge weg vom Endzustand
  • nur ein Übergang zwischen je zwei Zuständen
  • Übergänge beschriftet mit regulären Ausdrücken

Kontextfreie Grammatiken[edit]

  • ... Nonterminalsymbole (Variablen)
  • ... Terminalsymbole
  • ... Produktionen
  • ... Startsymbol
  • andere Notationen
    • Backus-Naur-Form (BNF)
    • Erweiterte Backus-Naur-Form (EBNF)
    • Syntaxdiagramme