Automatentheorie und Formale Sprachen - Mitschrift - Katoen/10.04.2007

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche
Back.png Zurück zu 05.04.2007 Book.png Hoch zu Inhaltsverzeichnis Forward.png Vor zu 17.04.2007

Inhaltsverzeichnis

Sprachen

Sprachen und Grammatiken und Automaten

SpracheGrammatikAutomatenmodell
0ohne RestriktionenTuringmaschine (DTM/NTM)
1kontextsensitivlinear beschr. Automaten (LBA)
2kontextfreieKellerautomaten (NKA)
det. KFLLR(k)-GrammatikenDKA
3reguläre Grammatiken, reguläre AusdrückeEndlicher Automat (DEA/NEA)

Abschlusseigenschaften

gegeben: Sprachen L1,L2 und L

1.) wenn L1 und L2 vom Typ i sind, gilt dann auch, dass L1 \underline{op} L2 vom Typ i sind?
2.) wenn L \in Typ i, ist dann auch \underline{op} L vom Typ i? \underline{op}\in\{*,\bar{ }\}

Seien G1 = (V1,Σ,P1,S1) und G2 = (V2,Σ,P2,S2) Grammatiken mit denselben Terminalalphabeten. Nehme o.E. an V_{1}\cap V_{2} = \oslash

1.) Vereinigung G_{1}\cup G_{2}=(V,\Sigma,P,S)
V=V_{1}\cup V_{2}\cup\{S\} wobei S\notin V_{1}\cup V_{2}
P=P_{1}\cup P_{2}\cup\{S\rightarrow S_{1}, S\rightarrow S_{2}\}
Dann gilt L(G_{1}\cup G_{2})=L(G_{1})\cup L(G_{2}).
Weiter gilt: Sind G1 und G2 vom Typ i, dann ist auch G_{1}\cup G_{2} vom Typ i(1,2,3)

2.) Konkatenation G_{1}\circ G_{2}=(V,\Sigma,P,S),
wobei V=V_{1}\cup V_{2}\cup\{S\} mit S\notin V_{1}\cup V_{2}
P=P_{1}\cup P_{2}\cup \{S\rightarrow S_{1}S_{2}\}
dann gilt: L(G_{1}\circ G_{2})=L(G_{1})\circ L(G_{2})
weiter gilt: sind G1 und G2 vom Typ i, dann ist auch G_{1}\circ G_{2} vom Typ i(0,1,2) [nicht für i=3]

3.) Kleeneabschluss. Sei G = (V,Σ,P,S) eine Grammatik. Sei G' = (V',Σ,P',S'),wobei V'=V\cup\{S'\}, S'\notin V.
Es folgt L(G') = L(G) * P'=P\setminus\{ S \to \epsilon \} \cup\{S'\rightarrow\epsilon, S'\rightarrow SS'\}.
Ist G vom Typ 2, so ist auch G' vom Typ 2. Genauso, ist G vom Typ 1,
so ist auch G' vom Typ 1.


Bsp.: Sei S\rightarrow 0|1|...|9 L(G) = {0,1,...,9}br>
1) Sei G^{*} = (V \cup \{S_*\}, \Sigma, P', S_*) mit den Regeln in P und zusätzlich S_{*}\rightarrow\epsilon|S|SS_{*}. Dann gilt: L(G * ) = L(G) * (alle Ziffernfolgen)
2) Sei G^+ = (V \cup \{S_*, S_+\}, \Sigma, P'', S_+) mit den Regeln in G * und zusätzlich S_{+}\rightarrow SS_{*}. Dann gilt: L(G^{+})=L(G)\circ L(G^{+}) = L(G)\circ L(G)^{+} = L(G)^{*}br>

\cap \cup \bar{ } \circ *
Typ 0 ( + ) + ( − ) + +
1 ( + ) + ( + ) + +
2 ( − ) + ( − ) + +
3 ( + ) + ( + ) ( + ) ( + )

() = Kommt noch
+ = abgeschlossen unter diesem Operator
- = nicht abgeschlossen

Satz

\mbox{Für }K, L \subset\Sigma^{*}:(K\cup L)^{*}=(K^{*}L)^{*}K^{*}

Beweis

\supset ist trivial
\subset: w\in (K\cup L)^{*}. w kann zerlegt werden w=w_{1}w_{2}\cdots w_{n} mit:

Fall 1

kein w_{i}\in L. Dann w\in K^{*} und klar w\in (K^{*}L)^{*}K^{*}

Fall 2

es gibt w_{i}\in L. Gruppiere die Segmente wi jeweils bis zum nächsten w_{k}\in Lbr> \underbrace{w_{i}}_{\in L}\underbrace{w_{i+1}w_{i+2}\cdots w_{k-1}}_{\in K}\underbrace{w_{k}}_{\in L} damit erhalten wir "`Blöcke"' in K * L. Nach dem letzten Block folgen evtl. noch K-Segmente (kein w_{i}\in L) damit w\in(K^{*}L)^{*}K^{*}.

wichtige Entscheidungsprobleme für Grammatiken:
1. Wortproblem (WP):
Gegeben: w\in\Sigma^{*} und eine Grammatik für L\subseteq\Sigma^{*} vom Typ i.
Gefragt: gilt w\in L?

2. Leerheitsproblem (LP):
Gegeben: eine Grammatik G vom Typ i
Gefragt: L(G)= \oslash?

3. Äquivalenzproblem (ÄP):
Gegeben: Grammatiken G1 und G2 (über Σ < math > )vomTypi < br > Gefragt:gilt < math > L(G1) = L(G2)?

WP LP ÄP
Typ 0 − − −
1 + − −
2 + O(n3) + O( | G | ) −
3 + O(n) + O( | G | ) + O( | G | )

+ = das Problem ist entscheidbar

Reguläre Ausdrücke

Sei Σ ein Alphabet. Die Menge der regulären Ausdrücke über Σ ist wie folgt definiert.

* \emptyset und ε sind RA
* für a\in \Sigma ist a ein RA
* wenn α und β RA sind, dann sind auch αβ, α + β und α *  RA
* nichts sonst ist ein RA

Definition - Semantik von regulären Ausdrücken

    * L(\emptyset)=\emptyset

    * L(a) = {a}

    * L(ε) = {ε}

    * L(\alpha+\beta)=L(\alpha)\cup L(\beta)

    * L(\alpha \beta)=L(\alpha) \circ L(\beta)

    * L(α * ) = L(α) *

Beispiel

* L(a+b^{*})=L(a)\cup L(b^{*})=\{a\}\cup L(b)^{*}
   =\{a\}\cup\{\epsilon, b, bb, bbb, \cdots\}

* L((a+b)^{*})=L(a+b)^{*}=(L(a)\cup L(b))^{*}=(\{a\}\cup \{b\})^{*}=\{a,b\}^{*}

* ab * (c + ε) alle Wörter die:

    1) mit einem a anfangen

    2) gefolgt durch beliebig viele b's

    3) abschließend optionell ein c

* L(ab^{*}(c+\epsilon))=\{a\} \circ \{b\}^{*} \circ \{\epsilon,c\}

Downloads

PDF-Version

Von „http://wiki.infostudium.de/wiki/Automatentheorie_und_Formale_Sprachen_-_Mitschrift_-_Katoen/10.04.2007“