Automatentheorie und Formale Sprachen - Mitschrift - Katoen/05.04.2007

Aus Infostudium Wiki

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

Inhaltsverzeichnis

Formale Sprachen, Automaten, Prozesse vom 05. April 2007

Grammatiktypen

Definition

Grammatiken G1 und G2 (beide über demselben Alphabet Σ) heißen äquivalent falls L(G1) = L(G2)

Definition

Sei G = (V,Σ,P,S) eine Grammatik. G heißt:

  • Kontextsensitiv (Typ 1) wenn für alle Regeln u\rightarrow v\in P gilt: |u|\leq|v|
Dies ist eine vereinfachte Definition. Verwenden sollte man jedoch die endgültige Definition.
  • Kontextfrei (Typ 2) wenn P\subset V\times\left(V\cup\Sigma\right)^{*}
  • Regulär (Typ 3) wenn P\subset V\times\left(\{\epsilon\}\cup \Sigma V\cup\Sigma\right)

KFG: jede Regel hat die Form A\rightarrow v

Reguläre Grammatik: jede Regel hat die Form

A\rightarrow\epsilon

A\rightarrow a

A\rightarrow aB

Beispiele

Sei Σ = {a,b,c} V = {S,A,B}

1. Beispiel

   S\rightarrow AS|ccSb

   cS\rightarrow a

   AS\rightarrow Sbb

   cSb\rightarrow c

   nicht von Typ 1, da z.B. cS\rightarrow a: |cS|>|a|

   nicht von Typ 2, \underbrace{cS}_{\notin V}\rightarrow a

   nicht von Typ 3, aus selbigem Grund

2. Beispiel

   S\rightarrow aAb

   aA\rightarrow Abc

   Abc\rightarrow aacc

   vom Typ 1, da |u|\leq|v|\forall u\rightarrow v\in P

   weder Typ 2, noch Typ 3, da aA\notin V

3. Beispiel

   S\rightarrow AB

   A\rightarrow aBb|Abc|bc

   B\rightarrow A

   Typ 1, da |u|\leq|v|\forall u\rightarrow v\in P

   Typ 2, da jede linke Seite von u\rightarrow v\in P ist in V.

   nicht Typ 3, da z.B. A\rightarrow aBb nicht das richtige Format hat

4. Beispiel

   S\rightarrow b

   A\rightarrow \epsilon|a|aA|aS

   ist vom Typ 0,2,3
   nicht von Typ 1, da A\rightarrow \epsilon \in P,  aber  | A |  = 1 und  | ε |  = 0

Typische Kontextsensitive Regeln

xAy\rightarrow xwy\mbox{ }A\mbox{ in Kontext } x\cdots y\mbox{ wird ersetzt durch w}

\underline{a}A\underline{B}\rightarrow cAd\mbox{ eine Änderung des Kontextes}

Kontextfreie Grammatiken

   A\rightarrow v_{1}|\cdots |v_{n} wird häufig als

   A::=v_{1}|\cdots|v_{n}

   Backus-Naur-Form (BNF) bezeichnet

Definition

Eine Sprache L ist von Typ i, falls es eine Grammatik G von Typ i gibt, sodass L(G) = L ist. 

   G:S\rightarrow abc|aAbc

   Ab\rightarrow bA

   Ac\rightarrow bA

   Ac\rightarrow Bbcc

   bB\rightarrow Bb

   aB\rightarrow aaA|aa

Diese Grammatik ist vom Typ1, jedoch nicht vom Typ 2 oder Typ 3.


Behauptung

L(G) = {anbncn}

Beweis

"\supseteq" Wörter von der Form anbncn sind ableitbar aus S


Wir zeigen mit Hilfe der Induktion, dass S\Rightarrow^{*}a^{i}Bb^{i+1}c^{i+1} für i > 0 ist.

Dann gilt auch, wegen aB\rightarrow aa, dass S\Rightarrow^{*}a^{i}b^{i}c^{i}a


Basis

i=1: S\Rightarrow aAbc\Rightarrow abAc\Rightarrow abBbcc\Rightarrow aBbbcc = a^{1}Bb^{2}c^{2}

Induktionsschritt

\mbox{I.V.:} S\Rightarrow^{*}a^{i}Bb^{i+1}c^{i+1}|i\geq 1

Finde eine Ableitung für ai + 1Bbi + 2ci + 2.

\underbrace{a^{i}Bb^{i+1}c^{i+1}}_{i\geq 1} = a^{i-1}aBb^{i+1}c^{i+1}\Rightarrow a^{i-1}aaAb^{i+1}c^{i+1}\Rightarrow a^{i+1}bAb^{i+2}c^{i+2}

\Rightarrow^{*}a^{i+1}b^{i+1}Ac^{i+1}\Rightarrow a^{i+1}b^{i+1}Bbccc^{i}\Rightarrow^{*} a^{i+1}Bb^{i+2}c^{i+2}

"\subseteq": nur Wörter von der Form anbncn ableitbar aus S.

Zeige, dass S\Rightarrow^{*}w impliziert w = anbncn für ein n\geq 1.

Fallunterscheidung

  • S\Rightarrow abc ok
  • S\Rightarrow aAbc\Rightarrow abAc\Rightarrow abBbcc\Rightarrow aBbbcc\Rightarrow aBb^{2}c^{2}


Beobachtung:

   a^{i}Bb^{i+1}c^{i+1}\Rightarrow a^{i+1}b^{i+1}c^{i+1}\left(\mbox{benutze }aB\rightarrow aa\right)

oder: 

   a^{i}Bb^{i+1}c^{i+1}\Rightarrow a^{i+1}Ab^{i+1}c^{i+1}\left(\mbox{benutze }aB\rightarrow Aaa\right)

Wieder beweisen,A loswerden. 

   a^{i+1}Ab^{i+1}c^{i+1}\Rightarrow^{*}a^{i+1}b^{i+1}Ac^{i+1} \mbox{einzige Möglichkeit!}

   \Rightarrow a^{i+1}b^{i+1}Bbc^{i+2}

   \Rightarrow a^{i+1}Bb^{i+2}c^{i+2}

   \Rightarrow a^{i+2}b^{i+2}c^{i+2}

(Bem.: alle Ableitungsschritte sind eindeutig) 


   Jede Typ 3 Sprache ist auch Typ 2.
   Ist dann auch jede Typ 2 Sprache vom Typ 1?
   Jede Typ 1 Sprache ist auch Typ 0.

Kleine Anpassung für die Definition von Typ 1 Sprachen: (|u|\leq|v|)\rightarrow\epsilon ist nicht ableitbar.

Definition

G = (V,Σ,P,S) mit \epsilon\in L(G) heißt Kontextsensitiv (Typ 1), falls

  • S\rightarrow\epsilon
  • \forall u\rightarrow v\in P\backslash\{S\rightarrow\epsilon\} gilt |u|\leq|v| und S kommt nicht in V vor.

Satz

Jede Typ 2 Grammatik ist von Typ 1

Beweis

  • Transformation einer KFG wandelt in eine ε -freie KFG um (d.h. a\rightarrow\epsilon , dann A = S . Falls S\rightarrow\epsilon , dann gibt es keine A\rightarrow v , sodass S\in V).
  • jede ε -freie KFG ist von Typ 1 (jede Regel A\rightarrow V in einer ε -freien KFG erfüllt \underbrace{|A|}_{1}\leq v für A\neq S )
Von „http://wiki.infostudium.de/wiki/Automatentheorie_und_Formale_Sprachen_-_Mitschrift_-_Katoen/05.04.2007“