Die Mathe-Redaktion - 19.07.2019 10:49 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 492 Gäste und 19 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Pumping-Lemma - kann einen Schritt nicht nachvollziehen
Druckversion
Druckversion
Autor
Schule J Pumping-Lemma - kann einen Schritt nicht nachvollziehen
Zrebna
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.09.2018
Mitteilungen: 176
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-06-19


Hi!

Folgende Aufgabe incl. Musterlösung (relevante Aufgabe rot markiert, als auch mein Verständnis-Problembereich).



Wieso wird hier als Faktor die 2 verwendet und wie kommt es hier zum Widerspruch der Grundannahme, dass die Sprache regulär ist?

Ich wäre eher so vorgegangen:
fed-Code einblenden

Ich hätte vorher das Wort zerlegt in:
fed-Code einblenden

Gemäß ersterer Übelregung wäre nun:
fed-Code einblenden

Da jedoch Länge von y >= 1 gem. PL ist die ursprüngliche Form des gewählten Wortes verletzt -> Annahme falsch -> Sprache nicht regulär.

Wo liegt mein Fehler und wie geht die Musterlösung vor?

Gruß,
Zrebna






  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2085
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-06-19


Du begründest nicht formal, warum das gepumpte Wort nicht zur Sprache gehört. (es ist ja auch offensichtlich)

Die Musterlösung rechnet das vor.

Es gibt $k-|y|$ 0-en.
Das Doppelte davon ist $2(k-|y|)$ und das ist für $|y|\geq 1$ etwas anderes als das geforderte $2k$.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.07.2004
Mitteilungen: 837
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-06-19


Hallo Zrebna,

2019-06-19 17:33 - Zrebna im Themenstart schreibt:
Wieso wird hier als Faktor die 2 verwendet und wie kommt es hier zum Widerspruch der Grundannahme, dass die Sprache regulär ist?

Die Wörter der Sprache besitzen ja die Eigenschaft, dass doppelt so viele 1'en wie 0'en enthalten sind.
Es ist also zu prüfen ob 2 * #{Nullen in xy^0z} =  #{Einsen in xy^0z}
(Das sind in der Musterlösung die beiden Enden der Gleichung, 2*(k-|y)) und 2k.)
Da durch die Konstruktion nur Nullen in y vorhanden sein können, schrumpft im Vergleich zu xyz in xy^0z nur die Anzahl der Nullen.


Ich wäre eher so vorgegangen:
fed-Code einblenden

Ich hätte vorher das Wort zerlegt in:
fed-Code einblenden

Gemäß ersterer Überlegung wäre nun:
fed-Code einblenden
Da jedoch Länge von y >= 1 gem. PL ist die ursprüngliche Form des gewählten Wortes verletzt -> Annahme falsch -> Sprache nicht regulär.
Hier liegt ein kleiner typischer Fehler vor. Du darfst die Zerlegung des Wortes in x, y und z ja nicht selber wählen, sondern musst alle Varianten gemäß der Pumping Lemma-Bedingungen betrachten. Du hast zwar kein festes Wort gewählt (ganz falsch), dich aber unzulässiger weise auf |xy|=k eingeschränkt.
Aber es gibt auch noch die Fälle |xy|<k. Dann enthält z ebenfalls Nullen.
Letztlich ändert sich an der Argumentation in diesem Fall nichts, aber in anderen Sprachen kann das den Beweis erschweren.

Gruß,
Yggdrasil





[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Zrebna
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 25.09.2018
Mitteilungen: 176
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2019-06-20


Danke für beide Posts!

@Yggdrasil:

Vielen Dank, ich kann mit deinen Erläuterungen nun gut nachvollziehen, was da passiert ist.
Der PL-Beweis verwirrt mich noch etwas bzgl. der Tatsache, dass die PL-Zahl meist auch den Exponent von den einzelnen Zeichen darstellt.
Aber ich versuche mal mit deinen Überlegungen ein paaar weitere
PL-Aufgaben.
Evtl. wird es ja doch noch "Klick" machen ^^



  Profil  Quote  Link auf diesen Beitrag Link
Zrebna hat die Antworten auf ihre/seine Frage gesehen.
Zrebna hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]