Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
  Konstruiere Kellerautomaten für Komplement einer Sprache |
|
Chris311
Aktiv 
Dabei seit: 23.01.2008
Mitteilungen: 6571
Aus: Karlsruhe
 |      Themenstart: 2010-11-29 20:21
|
Hallo,
ich bearbeite folgende Aufgabe
  
\ Die eigentliche Aussage habe ich bereits auf anderem Wege gelöst, indem ich ausgenutzt habe, dass kontextfreie Sprachen abgeschlossen unter Vereinigung, nicht aber unter Schnitt sind. Allerdings frage ich mich schon den ganzen lieben langen Tag, wie dieser andere Ansatz funktioniert. Hat jemand eine Idee, wie ich einen solchen Kellerautomaten konstruieren kann? Man muss ja eigentlich einen KA konstruieren, der alle beliebigen Konkatenationen der Wörter a und \$ erkennt, ausser denen aus L. Somit sieht es für mich so aus, als sei es umso schwerer diesen KA zu konstruieren. D.h. wenn ich einen KA gefunden habe, der L^- erkennt, dann sollte sich doch auch einer finden lassen der L erkennt, was aber offensichtlich nicht sein kann. Jedenfalls komme ich auf keinen grünen Zweig bei meinen Überlegungen. Weiß jemand Rat?
Viele liebe Grüße
Chris
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
[ Nachricht wurde editiert von fed am 29.11.2010 20:22:27 ]
|
 Profil
 Quote
 Link |
apo
Aktiv 
Dabei seit: 24.11.2010
Mitteilungen: 131
Aus:
 | Beitrag No.1, eingetragen 2010-11-29 23:51
|
Hi
Punkt 1: pumping lemma für kfS anwenden, um zu zeigen das L nicht kf ist.
Punkt 2: pda bauen, der das Komplement von L akzeptiert, also von dem L von dem wir eben bewiesen haben, dass es nicht kf ist !!
Sollte 2. gelingen hast du bewiesen, dass kfS nicht abgeschlossen sind unter Komplementbildung. Abgeschlossen heisst ja, das man die Sprachklasse mit der Operation nicht "kaputtmacht". Daher dürfte 2 nicht möglich sein. Hier wäre ja L nicht kf und Komplement von L schon !
Angenommen du hast ne reg Sprache. Die sind da abgeschlossen. Also kannst du von jeder reg Sprache das Komplement nehmen und da hast immer noch ne reg Sprache und umgekehrt.
|
Profil
Quote
Link |
Chris311
Aktiv
Dabei seit: 23.01.2008
Mitteilungen: 6571
Aus: Karlsruhe
| Beitrag No.2, vom Themenstarter, eingetragen 2010-11-30 11:54
|
2010-11-29 23:51 - apo in Beitrag No. 1 schreibt:
Hi
Punkt 1: pumping lemma für kfS anwenden, um zu zeigen das L nicht kf ist.
Punkt 2: pda bauen, der das Komplement von L akzeptiert, also von dem L von dem wir eben bewiesen haben, dass es nicht kf ist !!
Sollte 2. gelingen hast du bewiesen, dass kfS nicht abgeschlossen sind unter Komplementbildung. Abgeschlossen heisst ja, das man die Sprachklasse mit der Operation nicht "kaputtmacht". Daher dürfte 2 nicht möglich sein. Hier wäre ja L nicht kf und Komplement von L schon !
Angenommen du hast ne reg Sprache. Die sind da abgeschlossen. Also kannst du von jeder reg Sprache das Komplement nehmen und da hast immer noch ne reg Sprache und umgekehrt.
Hallo apo,
danke für deine Antwort. Aber leider hast du mir auch hier kein Stück weitergeholfen...
Meine Frage war doch, wie ich einen solchen Automaten konstruieren kann!? Ich konnte noch keinen skizzieren. Darum geht es mir.
Grüße
Chris
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
|
Profil
Quote
Link |
apo
Aktiv
Dabei seit: 24.11.2010
Mitteilungen: 131
Aus:
| Beitrag No.3, eingetragen 2010-11-30 14:39
|
Profil
Quote
Link |
Chris311
Aktiv
Dabei seit: 23.01.2008
Mitteilungen: 6571
Aus: Karlsruhe
| Beitrag No.4, vom Themenstarter, eingetragen 2010-11-30 17:09
|
2010-11-30 14:39 - apo in Beitrag No. 3 schreibt:
Hi
ich mach dir mal einen zweig vor
a -> XX
mit dollar in nächsten Zustand
a,X ->
\eps
a,# -> Y#
a,Y -> YY
mit dollar in nächsten zustand, nur wenn X oder Y im Stack steht
hier kann Stack geleert werden, weil es egal ist wieviele a noch folgen es muss nur das 3. dollar da sein
im zweiten Zweig vernachlässigst du die ersten a's und prüfst, ob die Anzahl der letzten beiden a's verschieden ist.
[ Nachricht wurde editiert von apo am 30.11.2010 14:41:49 ]
Aus deiner Schreibweise werde ich nicht wirklich schlau. Kannst du das mal so aufschreiben wie es allgemein gehalten wird? Also z.B.:
\ \delta(s_0, a, \#) -> (s_1, XX)
Hierbei führt die Übergangsfunktion von Zustand s_0 in den Zustand s_1 und liest das Eingabezeichen a, dabei überschreibt es das Hashsymbol und ersetzt es durch ein XX.
Dann könnte ich deine Idee besser interpretieren.
Grüße
Chris
[ Nachricht wurde editiert von fed am 30.11.2010 17:10:03 ]
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
[ Nachricht wurde editiert von Chris311 am 30.11.2010 17:10:12 ]
|
Profil
Quote
Link |
TheBear
Senior 
Dabei seit: 31.01.2006
Mitteilungen: 1230
Aus:
| Beitrag No.5, eingetragen 2010-11-30 17:19
|
Hi Chris,
die Idee ist einfach:
Es gibt drei Möglichkeiten für ein Wort, das nicht in L liegt:
1. Das Wort enthält mehr oder weniger als 2 $-Zeichen.
2a. Das Wort ist von der Form ak$al$am mit k != l
2b. Das Wort ist von der Form ak$al$am mit k != m
Für alle drei Fälle kannst du leicht einen NKA (sogar einen DKA) bauen, der akzeptiert, wenn das Wort die angegebene Eigenschaft erfüllt. Diese NKAs kannst du dann einfach kombinieren zu einem Gesamt-NKA, der nichtdeterministisch einen aus den drei Fällen auswählt.
Gruß TheBear
|
Profil
Quote
Link |
apo
Aktiv 
Dabei seit: 24.11.2010
Mitteilungen: 131
Aus:
| Beitrag No.6, eingetragen 2010-11-30 18:33
|
Hi
genau so ;-)
das meinte ich auch mit den Zweigen.
Um das so hier abzutippen kann ich mir nachher eventl. die Zeit nehmen.
|
Profil
Quote
Link |
Chris311
Aktiv
Dabei seit: 23.01.2008
Mitteilungen: 6571
Aus: Karlsruhe
| Beitrag No.7, vom Themenstarter, eingetragen 2010-12-15 14:13
|
Danke für Eure Hilfen, das war genau der Ansatz, den wir auch in der Musterlösung angestrebt haben.
Viele liebe Grüße
Chris
-----------------
Ich höre, und vergesse.
Ich sehe, und erinnere.
Ich handle, und verstehe.
Konfuzius
|
Profil
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]