Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Pumping-Konstante minimal wählen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Pumping-Konstante minimal wählen
Schutze
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-10


Ich bräuchte mal Hilfe bei folgender Aufgabe:

Die Pumping-Konstante n soll für die beiden regulären Sprachen jeweils so gewählt werden, dass die Aussage des Pumping-Lemmas erfüllt ist.



Zu L1:

Mal abgesehen davon, dass ich die Verwendung des griechischen Alphabets hier sehr verwirrend finde, bin ich irritiert, da die Wortlänge ja hier begrenzt ist. Bislang hatten wir zum Pumpinglemma eben die typischen Beispiele, bei denen man zeigt, dass eine Sprache nicht regulär ist und n quasi beliebig groß (und sinnvoll) gewählt werden konnte.
Meine Überlegung war nun, dass die Worte alle mit einem Großbuchstaben beginnen, der Mittelteil bis zu einer gewissen Länge aufgepumpt werden kann und die Worte dann auf Zeta oder Ny enden.
Also würde ich sagen |u| muss mindestens gleich 1 sein und der Mittelteil wäre dann mein v für das gilt |v| >=1. Dann wäre |uv| ja mindestens 2. Das wäre auch mein Lösungsvorschlag. Allerdings liegt das Wort uw ja nicht in der Sprache, also sind nicht alle Eigenschaften erfüllt.

Zu L2:

Meine Überlegung ist hier ähnlich. Hier würde ich sagen aa^+ ist mein u mit |u| = 2 und (bb|ccc)^* mein v, wobei |v| hier ja mindestens 2 wäre (oder doch 3? Ich weiß nicht, ob ich für die Konstruktion sagen kann, ich wähle einfach immer bb). Hier wäre uw mit dieser Wahl auch Element von L2 und ich würde behaupten n muss also mindestens 4 sein, da |uv| = 4 und gelten muss |uv| <= n.


Ich würde mich freuen, falls jemand die Zeit findet, da mal drüber zu schauen und mir sagt, ob ich auf dem Holzweg bin, oder meine Gedanken zumindest in die richtige Richtung gehen. Anregungen und Ergänzungen sind natürlich auch gern gesehen.

Viele Grüße




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-11


Für endliche Sprachen:
- Alle endlichen Sprache sind regulär.
- Worte endlicher Sprachen können offenbar nicht gepumpt werden.
(sonst gäbe es automatisch unendliche viele Worte in der Sprache)

Ansatz:
Wähle als Pumpingkonstante die Länge des längsten Wortes + 1.
Ab dieser Länge erfüllt jedes Wort der Sprache das Pumpinglemma.



$L_2$ ist etwas anspruchsvoller.
Überlege dir, wie lang ein Wort mindestens sein muss, damit es mindestens eine pumpbare Einheit besitzt.
Wie lautet denn bspw. das kürzeste Wort der Sprache und kann man dieses pumpen?
Falls nein, wie lautet das längste Wort, das man nicht pumpen kann?


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-11


@DerEinfaeltige,
vielen Dank für deine Antwort.

Zu deinem Ansatz zu L1:
Wieso gelten die Aussagen des Pumping-Lemmas denn erst ab n = max. Wortlänge +1?

Ich habe hier scheinbar noch Verständnisprobleme.
Also ich kann in der Sprache nichts pumpen, soweit so gut.
Wenn ich nun sagen würde, n=1, dann gäbe es aber doch bereits für jedes Wort eine entsprechende Zerlegung, oder nicht?
Dann wäre |u|= 0, |v|=1, und somit |uv| <= n und w könnte so gewählt werden, dass uw in L1 liegt. Und es würde ja immer gelten |uvw| >= n.  

Aufgrund des scheinbaren Verständnisproblems kann ich aus deinen Fragen zu L2 auch nicht viel ableiten.
Das kleinste pumpbare Wort wäre hier aa(bb)^*ddd
Das kürzeste Wort, das nicht pumpbar ist, wäre aaddd
Das längste Wort das nicht pumpbar ist, kann unendlich lang sein, da die Sprache bereits durch a^+ nicht endlich ist.

Ich habe schon versucht, durch Recherche irgendwie schlauer daraus zu werden, aber das verläuft leider nicht besonders erfolgreich. Fast überall gibt es eben die entsprechende Definition des Lemmas und ein paar Beispiele zur Anwendung, aus denen ich in Bezug auf diese Art von Aufgabe nicht viel schlauer werde.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-05-11


Zu L1:
Es gibt in der Sprache Wörter der Länge $|w|\geq 1$, die sich nicht pumpen lassen.
Also kann $n=1$ unmöglich eine Pumpingkonstante sein.

"Pumpen" bedeutet ja, dass man einen nichtleeren Teil des Wortes beliebig vervielfältigt.
Das ist bei den Wörtern einer endlichen Sprache grundsätzlich nicht möglich, da diese nicht beliebig lang werden können.

Entsprechend gibt es auch keine gültige Zerlegung.

Kurzes Beispiel:
Das Wort $ab$ kann man nur dann zerlegen und pumpen, wenn entweder $a^*b$ oder $ab^*$ oder $(ab)^*$ komplett(!) in der Sprache liegen.
Ist das nicht der Fall, muss die Pumpingkonstante einer Sprache, die das Wort $ab$ enthält, größer als 2 sein.



PS.: Gibt es ein unendlich lange Wort, das man nicht pumpen kann, so kann die Sprache nicht regulär sein, da man in einer regulären Sprache gemäß Pumpinglemma alle unendlich langen Wörter pumpen kann.


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-11


Okay, ich glaube für die Sprache L1 ist der Funke nach längerem Nachdenken nun übergesprungen. Die Aussage ist durch die Wahl von dem vorgeschlagenen n leererweise erfüllt, richtig?

Jetzt wo ich nochmal auf die Sprache L2 schaue, bemerke ich auch, dass ich den RegEx falsch gelesen habe. Somit wäre das längste Wort, das nicht pumpbar ist ein Wort der Länge 6.
Liege ich dann richtig in der Annahme, dass hier n = 7 sein müsste?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2021-05-11


Ich komme auf ein nichtpumpbares Wort der Länge 10 (bspw. $aaddabccba$ kann man nicht pumpen) und die Pumpingkonstante 11.


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-05-11


Okay, jetzt bin ich doch etwas verwirrt, wie du auf dieses Wort kommst.
Ich habe ja einmal den linken Teil vom "Oder" und den rechten Teil.
Der linke Teil ist a^+a(bb|ccc)*ddd
Der rechte Teil a(bc|da)cba
Dein gewähltes Wort ist ja nun eine Konkatenation von beiden Teilen (wobei dir glaube ich ein d bei aaddd abhanden gekommen ist). Wenn ich nun ein Wort aus der Sprache bilde, muss ich mich aber doch entscheiden, welchen Teil des "Oders" ich wähle.
Wobei mich beim linken Teil irritiert, dass ich ja direkt am Anfang das a^+ habe. Das lässt sich ja nicht pumpen, da es nicht null mal vorkommen kann, aber kann ja trotzdem beliebig lang sein. Das würde aber dann deiner Aussage von vorhin widersprechen, dass das längste Wort, welches sich nicht pumpen lässt, nicht unendlich lang sein kann.

Beim rechten Teil des "Oders" ist das längste Wort ja z.B. abccba.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.10.2020
Mitteilungen: 35
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-11


Noch ein Nachtrag meinerseits. Mir fiel grade ein, dass a^+ sich ja auch schreiben lässt, als aa*. Demnach wäre das längste Wort im linken Teil des RegEX ja das Wort a.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-05-11

\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
2021-05-11 15:24 - DerEinfaeltige in Beitrag No. 3 schreibt:

PS.: Gibt es ein unendlich lange Wort, das man nicht pumpen kann, so kann die Sprache nicht regulär sein, da man in einer regulären Sprache gemäß Pumpinglemma alle unendlich langen Wörter pumpen kann.
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)

Es gibt keine unendlich langen Wörter.

Vorschlag: Gibt es zu jeder natürlichen Zahl \(n\) eine Zahl \(N\geqslant n\) so, dass in \(L\) ein nichtpumpbares Wort der Länge \(N\) liegt, dann ist \(L\) nicht regulär.

mfg
thureduehrsen


-----------------
sammeltlemmas.blogspot.de/

https://www.informatik.uni-kiel.de/~tdu/
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Schutze 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-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]