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

Aus VoWi
Zur Navigation springen Zur Suche springen

Reguläre Sprachen[Bearbeiten]

Operationen auf formalen Sprachen[Bearbeiten]

Seien L, L' \subset \Sigma^* zwei Sprachen.

Vereinigung
L \cup L' = \{w \mid w \in L \lor w \in L'\}
Verkettung
L \cdot L' = \{w \cdot w'\mid w \in L, w' \in L'\}
Potenzen
L^0 = \{\epsilon\}
L^{n+1} = L \cdot L^n \quad (n\ge 0)
L^+ = \bigcup_{n\ge 1} L^n
Kleene-Stern
L^* = \bigcup_{n\ge0} L^n = L^0 \cup L^+ = \{\epsilon\} \cup L^+

Definition regulärer Sprachen[Bearbeiten]

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[Bearbeiten]

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

─>A─>

Leersprache \{\} \emptyset
Leerwortsprache \{\epsilon\} \epsilon
───────>
Terminalsymbol \{s\} s "s" ─>s─>
Aufeinanderfolge X \cdot Y XY XY ─> X ─> Y ─>
Alternativen X \cup Y X + Y X|Y
 ╭─> X ─╮
─┤      ├─>
 ╰─> Y ─╯
Option \{\epsilon\} \cup X \epsilon + X [X]
 ╭─────╮
 │     v
─┴─ X ───>
Wiederholung ≥ 0 X^* X^* \{X\}
 ╭─ X <─╮
 v      │
────────┴─>
Wiederholung ≥ 1 X^+ XX^*,X^+ X\{X\}
 ╭──────╮
 v      │
─── X ──┴─>
Gruppierung (X) (X) (X)
  • Posix Extended Regular Expressions (ERE)

Eigenschaften regulärer Sprachen[Bearbeiten]

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

Vom regulären Ausdruck zum Automaten[Bearbeiten]

Vom Automaten zum regulären Ausdruck[Bearbeiten]

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[Bearbeiten]

G = \langle V, T, P, S\rangle

  • V ... Nonterminalsymbole (Variablen)
  • T ... Terminalsymbole
  • P\subseteq V \times (V \cup T)^* ... Produktionen
  • S \in V ... Startsymbol
  • andere Notationen
    • Backus-Naur-Form (BNF)
    • Erweiterte Backus-Naur-Form (EBNF)
    • Syntaxdiagramme