Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Hoch zu Inhaltsverzeichnis

Vor zu 05.04.2007

Inhaltsverzeichnis

1 Formale Sprachen, Automaten, Prozesse vom 03.04.2007
- 1.1 Formale Sprachen
- 1.2 Grammatiken

Formale Sprachen, Automaten, Prozesse vom 03.04.2007

Formale Sprachen

Alphabete und Worte

$Σ$ = Alphabet, d.h. eine endliche Menge von Symbolen.

$Σ b i n = {0,1}$

$\Sigma_{letter}=\{a,b,\cdots,z,A,B,\cdots,Z\}$

$\left|w\right|$ = Länge des Wortes $w$

$\left|w\right|_{a}$ = Anzahl von $a$ Symbolen in $w$

$ε$ = leeres Wort. $\left|\epsilon\right|=0$

Beispiel

    $Σ b i n = {0,1}$ 

    $w = 0100110110$ 

   

   

    $v = 011$

Konkatenation

$Σ *$ = Menge der endlichen Wörter über $Σ$

$Σ +$ = Menge der endlichen, nicht-leeren, Wörter über $Σ$

$\Sigma^{*} = \{a_{1}a_{2}\cdots a_{n}|n\in\mathbb{N}, a_{i}\in\Sigma\}$

Für $w=a_{1}a_{2}\cdots a_{n}$ und $v=b_{1}b_{2}\cdots b_{k}\in\Sigma^{*}$ dann $w\circ v = \underbrace{a_{1}\cdots a_{n}}_{w}\underbrace{b_{1}\cdots b_{k}}_{v}$ ist eine Konkatenation von $w$ und $v$ .

$\Sigma^{*}\times\Sigma^{*}\rightarrow\Sigma^{*}$

$ε$ ist neutrales Element für $\circ$ , da $w\circ\epsilon=w$ und $\epsilon\circ w=w$

$w\circ v\neq v\circ w$

$\left( w\circ v\right)\circ u=w\circ \left( v\circ u\right)$

Beispiel

Inverse

Inverse eines Wortes: $ε R = ε$

$\left( wa\right)^{R}=a\left(w^{R}\right)$

Wort $w$ mit $w R = w$ heißt ein Palindrom, z.b. $x = 101$ , $y = 0110$

Wort $w$ ist Präfix von $y$ falls $\exists x$ sodass $y = w x$

Wort $w$ ist Suffix von $y$ falls $\exists x$ sodass $y = x w$

Wort $w$ ist ein Teilwort von $y$ falls $\exists x_{1},x_{2}$ sodass $y = x 1 w x 2$

Sprachen

Eine Sprache über einem Alphabet $Σ$ ist eine Teilmenge $L\subseteq\Sigma^{*}$

Sprachen:

$L, L 1, L 2, L'$

$\bar{L}=\Sigma^{*} \setminus L$

$L_{1}\cup L_{2}, L_{1}\cap L_{2}$

$L_{1}\circ L_{2}=\{\underbrace{w_{1}w_{2}}_{\text{Konkatenation der Woerter}}|w_{1}\in L_{1}, w_{2}\in L_{2}\}$

$L_{1}\circ L_{2}\circ\cdots\circ L_{n}=\{w_{1}w_{2}\cdots w_{n}|w_{i}\in L_{i}, 0 < i\le n\}$

$L^{n}=\underbrace{L\circ L\circ\cdots L}_{n\text{ Mal}} \qquad L^{0}=\{\epsilon\} \qquad L'=L$

$L^{*}=\bigcup_{n\geq0}L^{n} \qquad L^{+}=\bigcup_{n\geq1}L^{n}$

$\epsilon\in L^{*}\mbox{ gdw }\epsilon\in L$

   Beispiel

Grammatiken

Definition

Grammatik: Gibt Regeln vor, nach denen Wörter einer Sprache generiert werden können.
Grundidee: Termersetzungsprozess = ersetze Zeichenketten (Terminalzeichen und Hilfesvariablen) durch andere Wörter, bis ein Wort entsteht das nur Symbole aus $Σ$ enthält.

Def.: Eine Grammatik $G= \left(V, \Sigma, P, S\right)$ bestehende aus

   einer endlichen Menge  $V$  von Variablen (=Nichtterminale, Nonterminale)
   einer endlichen Menge  $Σ$  von Terminalsymbolen, 
   einer endlichen Menge  $P$  von Produktionen 
   ein \textit{Startsymbol}

Beispiel

    $V = {A, B, S}$ 
    $Σ = {a, b}$ 
    $P =$

Abbildungsrelation $\Rightarrow$

Sei $G=\left(V,\Sigma,P,S\right)$ eine Grammatik, $x,y\in \left(V\cup\Sigma\right)^{*}$ .
$x\Rightarrow y$ gdw. $\exists\mbox{ }u,v,w,z\left(V\cup \Sigma\right)^{*}$ sodass $x = w u z$ $y = w v z$ und $u\rightarrow v$
$\Rightarrow^{*}$ = reflexive, transitive Hülle von $\Rightarrow$