Pumping-Lemma Typ2-Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:37 Sa 19.08.2006 | | Autor: | fnatter |
| Aufgabe | | http://www2.inf.fh-bonn-rhein-sieg.de/~fnatte2s/MK2A4.pdf |
Habe ich diese Pumping Lemma für kontextfreie Sprachen Aufgabe so richtig gelöst?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: [interne Webseite unserer Semesters]
|
|
| |
|
Hallo und guten Morgen,
sieht gut aus, der Ansatz ist richtig, ich hab nicht jedes Detail ganz genau nachgeprüft.
Stell doch bitte die Lösung direkt hier ins Forum und nicht nur den Link, denn falls der mal nicht mehr sein sollte, wäre dann
die gesamte Diskussion hier hinfällig, und das ist nicht die Idee des Matheraumes.
Viele Grüße,
Mathias
ps. Habe vermutlich Deinen Dozenten gestern auf einem Spielplatz getroffen. 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:52 Sa 26.08.2006 | | Autor: | fnatter |
meinst du Herrn Wirtgen?
Wärst du vielleicht so nett, den Fall 7 genauer anzuschauen?
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
Hallo fnatter,
sic est, Herrn Prof. Dr. Jürgen Wirtgen mein ich - weisst Du, woher ich ihn kenne ?
Zur Aufgabe:
Eine Sache stört mich stilistisch ein wenig. Du betrachtest 7 Fälle und argumentierst für jeden (incl. Fall 7), wie dann ein Widerspruch eintritt - und diese Argumentation
scheint mir richtig. Aber Du könntest meiner Ansicht nach noch einen Tick deutlicher machen, ob und weshalb diese Fälle alle Möglichkeiten abdecken.
Ich würd so argumentieren: Sei [mm] n_0 [/mm] das n, dessen Existenz aus der Annahme der Kontextfreiheit von L folgt.
Man kann bei [mm] a^mb^nc^{m+n} [/mm] die Zahlen m,n so gross wählen, dass [mm] n,m\geq 2n_0 [/mm] (zum Beispiel), dann ist wegen [mm] |vwx|\leq n_0 [/mm] entweder
vwx ein Teilstring (Du nennst es Infix) von [mm] a^mb^n [/mm] (nennen wir dies Fall 1) oder von [mm] b^nc^n [/mm] (Fall 2).
Es ist hierin auch direkt begründet, dass nur Fall1 oder Fall 2 auftreten kann (denn n,m wurden hinreichend gross gewählt).
Zu Fall 1:
Unterfälle:
(1.1) vwx Teilstring von [mm] a^n
[/mm]
(1.2) vwx = [mm] a^ib^j, \:\: i+j\leq n_0
[/mm]
(1.3) vwx Teilstring von [mm] b^n
[/mm]
Zu Fall 2:
Unterfälle:
(2.1) vwx Teilstring von [mm] b^n
[/mm]
(2.2) [mm] vwx=b^ic^j,\:\: i+j\leq n_0
[/mm]
(2.3) vwx Teilstring von [mm] c^{m+n}
[/mm]
Es ist hier direkt klar, dass dies die möglichen Fälle sind, und nun kann man jeden einzelnen ''verarzten''.
Bei den Fällen (1.2) und (2.2) kommt man dann sofort auf deine Fälle 4,5 bzw. 6,7.
Kurzum: Richtig ist es, man muss aber halt bei Fallunterscheidungen immer beweisen oder argumentieren, dass man keinen
Fall ausser acht gelassen hat.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:24 Mo 28.08.2006 | | Autor: | fnatter |
erzähl' mal woher du Herrn Wirtgen kennst.
|
|
|
| |
|
Hallo fnatter,
siehe PN zu dieser Frage.
Gruss,
Mathias
|
|
|
|
