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

1. Aussagenlogik
2. Endliche Automaten
3. Formale Sprachen und Grammatiken
4. Prädikatenlogik
5. Petri-Netze

Reguläre Sprachen

• Media:TU Wien-Formale Modellierung VU (Salzer) - Folien 2019S 06.pdf

Operationen auf formalen Sprachen

Seien $L,L^{\prime }\subset {\Sigma }^{\ast }$ zwei Sprachen.

Vereinigung

$L\cup L^{\prime }=\{w\mid w\in L\vee w\in L^{\prime }\}$

Verkettung

$L\cdot L^{\prime }=\{w\cdot w^{\prime }\mid w\in L,w^{\prime }\in L^{\prime }\}$

Potenzen

$L^0=\{ϵ\}$

$L^{n+1}=L\cdot L^n(n\ge 0)$

$L^{+}=\bigcup _{n\ge 1}{L}^n$

Kleene-Stern

$L^{\ast }=\bigcup _{n\ge 0}{L}^n=L^0\cup L^{+}=\{ϵ\}\cup L^{+}$

Definition regulärer Sprachen

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

• algebraische Notation

Operatorrangfolge (absteigend): *, +

• EBNF-Notation
• Syntaxdiagramme

	Reg. Sprache	Algebra	EBNF	Syntaxdiagramm
Abkürzung	$A$	$A$	$A$	─>A─>
Leersprache	$\{\}$	$\mathrm{\varnothing }$
Leerwortsprache	$\{ϵ\}$	$ϵ$		───────>
Terminalsymbol	$\{s\}$	$s$	"s"	─>s─>
Aufeinanderfolge	$X\cdot Y$	$XY$	$XY$	─> X ─> Y ─>
Alternativen	$X\cup Y$	$X+Y$	$X|Y$	╭─> X ─╮ ─┤ ├─> ╰─> Y ─╯
Option	$\{ϵ\}\cup X$	$ϵ+X$	$[X]$	╭─────╮ │ v ─┴─ X ───>
Wiederholung ≥ 0	$X^{\ast }$	$X^{\ast }$	$\{X\}$	╭─ X <─╮ v │ ────────┴─>
Wiederholung ≥ 1	$X^{+}$	$X{X}^{\ast },X^{+}$	$X\{X\}$	╭──────╮ v │ ─── X ──┴─>
Gruppierung	$(X)$	$(X)$	$(X)$

• Posix Extended Regular Expressions (ERE)

Eigenschaften regulärer Sprachen

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

Vom Automaten zum regulären Ausdruck

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

• Media:TU Wien-Formale Modellierung VU (Salzer) - Folien 2019S 07.pdf

$G=⟨V,T,P,S⟩$

• $V$ ... Nonterminalsymbole (Variablen)
• $T$ ... Terminalsymbole
• $P\subseteq V\times (V\cup T{)}^{\ast }$ ... Produktionen
• $S\in V$ ... Startsymbol

• andere Notationen
  • Backus-Naur-Form (BNF)
  • Erweiterte Backus-Naur-Form (EBNF)
  • Syntaxdiagramme