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'\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\geq 0)$

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

Kleene-Stern

$L^{*}=\bigcup _{n\geq 0}L^{n}=L^{0}\cup L^{+}=\{\epsilon \}\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	$\{\}$	$\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

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=\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