Die Mathe-Redaktion - 10.12.2018 14:33 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
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 840 Gäste und 22 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 bei nicht reg. Automaten (Verständnisproblem)
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Pumping-Lemma bei nicht reg. Automaten (Verständnisproblem)
gentos
Neu Letzter Besuch: im letzten Monat
Dabei seit: 16.11.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-11-16 12:50


Hallo,
ich habe folgende Aufgabe gegeben. (Siehe Unten)

Bei 11.1) soll ich ja zeigen, dass die reg. PE für L1 gilt.
L1 besteht dabei aus der Vereinigung der Sprache L(...) und (nennen wir die mal L2) "|w| ist Primzahl".
Das die reg. PE für L gilt ist auf den ersten Blick irgendwie klar. Mich verwirrt jetzt nur L2. Da L2 so weit ich weiß nicht reg. ist, müsste doch auch die reg. PE nicht gelten.

Und da L1 quasi auch alle Wörter aus L2 beinhaltet und die reg. PE für alle Wörter aus L1 gelten muss, passt das doch nicht ganz.

Und soweit ich das sehe ergänzt L L2 auch nicht wirklich, da in L2 nicht unbedingt "aa" oder "bb" vorkommen muss.

Wo liegt mein Fehler?
Und wie würde ich dann 11.2) zeigen?


Danke schonmal

hier die Aufgabe:



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-11-16 13:27


Das reguläre Pumpinglemma ist nur eine notwendige Bedingung für Regularität. (genau darum geht es ja hier)

Das Pumpinglemma kannst du hier immer erfüllen, indem du aus einer Dreiergruppe einen einzelnen Buchstaben auswählst und entweder etfernst oder pumpst.


Für 11.2 kann man bspw. Jaffes Pumping Lemma verwenden.


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



  Profil  Quote  Link auf diesen Beitrag Link
gentos
Neu Letzter Besuch: im letzten Monat
Dabei seit: 16.11.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-11-16 22:46


Aber wie ist es dann mit den Worten, die nur in {w ∈ {a,b}* | |w| ist Primzahl} liegen?
So weit ich mich erinnern kann, konnte man die Wörter nicht Pumpen, da der Abstand zwischen 2 Primzahlen ja irgendwann beliebig groß wird.
Und eben diese Wörter liegen ja dann in L.



  Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 1949
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-11-17 08:45

\(\begingroup\)
2018-11-16 22:46 - gentos in Beitrag No. 2 schreibt:
Aber wie ist es dann mit den Worten, die nur in {w ∈ {a,b}* | |w| ist Primzahl} liegen?
So weit ich mich erinnern kann, konnte man die Wörter nicht Pumpen, da der Abstand zwischen 2 Primzahlen ja irgendwann beliebig groß wird.
Und eben diese Wörter liegen ja dann in L.

Du musst ja nicht zu einer Primzahl pumpen.
Es reicht, durch pumpen ein $a$ oder $b$ zu verdoppeln.
Und das geht ab einer gewissen Mindestlänge (3 Buchstaben) immer.

Liegt das Wort nicht nur in $L_2$, sondern auch in $L$, gibt es kein Problem.

Kritisch ist nur:
$ababababa\dots$ bzw. $babababab\dots$ mit Primzahllänge.

Hier kann man den zweiten Buchstaben pumpen und das Wort verbleibt immer in der Sprache, da es dadurch entweder $aa$ bzw. $bb$ erhält oder (für $i=1$) unverändert mit Primzahllänge bleibt.



Mit den hinreichend Pumping Lemmata funktioniert das nicht.
Bei Jaffes Pumpinglemma kann man bspw. zeigen, dass die Rückrichtung (Gepumptes Wort $uv^iwx$ in Sprache $\Rightarrow$ Wort $zx$ in Sprache) im Allgemeinen nicht stimmt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
gentos hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    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-2018 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]