www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Formale Sprachen" - L kontextfrei => L^c ktf ?
L kontextfrei => L^c ktf ? < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

L kontextfrei => L^c ktf ?: Im Beweis muss nen Fehler sein
Status: (Frage) überfällig Status 
Datum: 18:23 Fr 21.11.2008
Autor: Rheinsi

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

Hallo!

Habe eine Frage zu einem Beweis von mir!

Aufgabe war:

Wenn L [mm] \subseteq \Sigma [/mm] * kontextfrei ist, ist dann auch [mm] \Sigma [/mm] * \ L kontextfrei?


Meine Lösung:

L [mm] \subseteq \Sigma [/mm] * kontextfrei. Es gilt [mm] \Sigma [/mm] * \ L = [mm] L^c [/mm]

w [mm] \in \L^c \gdw [/mm] w [mm] \notin [/mm] L [mm] \forall [/mm] w [mm] \in \Sigma [/mm] *

Eine Sprache S ist genau dann kontextfrei, wenn es einen Kellerautomaten B gibt, der genau S akzeptiert (Skript s. 24) "Zitat Skript: (....) wollen wir nun eine Klasse von verallgemeinerten Automaten definieren, die genau die kontextfreien Sprachen realisieren. Die Automaten sind die "Kellerautomaten", die es in deterministischer und nichtdeterministischer Variante gibt. (...) "

Sei A nun der Kellerautomat, der genau L akzeptiert mit

A = (Q, [mm] \Sigma, \Gamma [/mm] , [mm] \delta, q_{0} [/mm] , [mm] F_{A} [/mm] )

Beh: B = (Q, [mm] \Sigma, \Gamma [/mm] , [mm] \delta, q_{0} [/mm] , Q \ [mm] F_{A} [/mm] ) akzeptiert genau [mm] L^c \gdw [/mm] B akzeptiert alle w [mm] \notin [/mm] L


Bew:
zz. w [mm] \notin [/mm] L [mm] \gdw [/mm] B akzeptiert w

" => "

es existiert keine Zustandsfolge [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit m= lh(w)
und 1.) [mm] q_{n_{m}} \in F_{A} [/mm]  2.) [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und 3.) [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m

=> für alle Folgen [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit m= lh(w) und  [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und  [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m
gilt [mm] q_{n_{m}} \in F_{A}^c [/mm] = Q \ [mm] F_{A} [/mm]

Mit der Existenz einer solchen Folge folgt

=> B akzeptiert w




" <= "

es existiert eine Zustandsfolge [mm] q_{n_{0}},.....,q_{n_{m}} [/mm] mit
1.) [mm] q_{n_{m}} \in F_{A}^c [/mm] = Q \ [mm] F_{A} [/mm]  2.) [mm] q_{n_{0}} [/mm] = [mm] q_{0} [/mm] und 3.) [mm] \delta (q_{n_{i}}, w_{i}, x_{i}) [/mm] = [mm] q_{n_{i+1}} [/mm] für 0 [mm] \le [/mm] i < m


=> w [mm] \in L^c [/mm]  <=> w [mm] \notin [/mm] L


=> Behauptung

Es existiert also ein Kellerautomat, der genau [mm] L^c [/mm] = [mm] \Sigma [/mm] \ L akzeptiert

=> [mm] \Sigma [/mm] \ L ist kontextfrei.



Soweit zu meinem Beweis. Der muss irgendwo kaputt gehen, kann mir wer sagen, wo?

Der Gegenbeweis sieht so aus:

Sei L = [mm] L_{1} \cap L_{2} [/mm] , [mm] L_{1} [/mm] und [mm] L_{2} [/mm] kontextfrei.

Annahme: [mm] L_{1}^c [/mm] ist kontextfrei, so auch [mm] L_{2}^c [/mm] und auch [mm] L_{1}^c \cup L_{2}^c [/mm] (Haben wir bewiesen). [mm] L_{1}^c \cup L_{2}^c [/mm] ist aber [mm] L^c. [/mm] Nach Annahme ist also [mm] (L^c)^c [/mm] auch kontextfrei. => L = [mm] (L^c)^c [/mm] kontextfrei, das hatten wir aber gezeigt, dass das nicht so sein muss!
=> Widerspruch => L muss nicht kontextfrei sein!



Meine Vermutung ist ja, dass der Satz aus dem Skript falsch sein muss, kann mir aber nicht erklären warum. Habe ich ihn falsch gedeutet?!

Über Antworten würde ich mich freuen!


        
Bezug
L kontextfrei => L^c ktf ?: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:43 So 23.11.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]