Alphabete

Neue Frage »

prinzschleifer Auf diesen Beitrag antworten »
Alphabete
Guten Morgen,

ich mach grade eine Aufgabe und bin mir nicht sicher ob ich sie richtig bearbeite, also hier meine Frage:

Es sei . Die Sprache sei definiert durch .
Welche der folgenden Wörter sind in der formalen Sprache enthalten? Geben
Sie für jedes Wort w, das in liegt, eine Zerlegung in Wörter aus L
an, so dass

Ende der Aufgabe.

So ich hab erstmal einbisschen konateniiert smile

Dabei ist




So und weiter will ich nichts ausführen, befor ich nicht weiß ob es richtig ist was ich mache ^^. Also das bedeutet doch schlichtweg, dass ich das beliebig oft benutzen darf.

So das erste Wort das ich beschreiben soll ist.


Ich bin mir jetzt nicht sicher was ich dazuschreiben soll.



oder was soll ich schreiben?

Theorätisch könnte ich auch alles in packen, da ja , also das leere Wort entählt und ich dadurch beliebeige a weglassen kann. Auch richtige Schlussfolgerung?

Wäre gut, wenn da mal jemand einen Blick drüber Werfen könnte.

Vielen Dank!
Abakus Auf diesen Beitrag antworten »
RE: Alphabete
Zitat:
Original von prinzschleifer


Sieht bei dir ziemlich kompliziert aus, was hälst du von diesem:



Die b's markieren dir dann die Art und Weise, wie du Wörter zerlegen kannst.

Grüße Abakus smile
prinzschleifer Auf diesen Beitrag antworten »

Jo, ich hab den Fehler gemacht, dass ich das in die Klammer geholt hab und angefangen hab damit die Wörter zu verbinden, was falsch ist.

Gut, also jetzt zum Beispiel:




So nächstes Beispiel:





Dies lässt dich nicht ausdrücken, da die Folge in keinem vorkommt.





Sieht mal richtig aus, oder? Ist die Notation auch korrekt?
Reksilat Auf diesen Beitrag antworten »

Ich glaube nicht, dass Du die benötigst.
Es ist und dieses Wort kannst Du in und zerlegen, wobei und ist.
prinzschleifer Auf diesen Beitrag antworten »

Das macht die Aufgabe ja recht einfach, das Ergebnis ist aber dennoch das gleiche,
lässt sich nicht darstellen.


Okay, das war erst die Aufwärmübung.

Nächste Aufgabe, wo ich ein bisschen Probleme habe, wie ich da ranngehn soll. Wäre nett wenn ihr mir hier ein paar Denkanstöße geben könntet.

Es sei . Die Sprache sei definiert durch . Zeigen Sie, dass jedes Wort w aus , das mindestens einmal das Zeichen b enthält, in L liegt.

Tipp:
Führen Sie eine Induktion über die Anzahl der Vorkommen des Zeichens b in w durch.

Ende der Aufgabenbeschreibung

Okay, also mir is klar, dass ich zeigen soll, dass wenn das Wort w mindestens ein b enthält auch gleich in L liegt. Wie kann ich aber formal angeben wie oft ein Symbol in einem Wort vorkommt?

Also, ich hab das ganze schonmal umgeschrieben, dann erhalte ich für
prinzschleifer Auf diesen Beitrag antworten »

Nachtrag aus vorigem Post

wobei und sein muss.

Ist das nicht kompletter Unfug? Dadurch könnte man ja gar nicht w = abba ausdrücken traurig irgendwas mach ich falsch

Das selbe für L:
und
 
 
Reksilat Auf diesen Beitrag antworten »

Eine Möglichkeit das aufzuschreiben wäre:

Das aber nur als Idee, denn so wirst Du noch nicht so gut mit Induktion herankommen. Mit eine wenig Herumgebastele hat b dann in jedem Faktor die Potenz 1 und so lässt sich dann auch eine schöne Induktion nach n vollführen.
prinzschleifer Auf diesen Beitrag antworten »

Also soll ich nicht als Ausgangspunkt verwenden sonder was ganz anders?

Ich komm nämlich grad auf keine andere Dartsellung wo ich b in jedem Faktor die Potenz 1 hat. traurig

Nach Vorraussetzung soll ja grade b einmal in dem Wort w vorkommen, also muss ich es ja erzwingen, dass die Potenz oben mindestens einmal 1 wird.

Sprich:
Reksilat Auf diesen Beitrag antworten »

Und wenn Du jetzt setzt, was müsstest Du dann verändern um wieder auf zu kommen?
prinzschleifer Auf diesen Beitrag antworten »

Einfach eine zweite Hilfsvariable einführen und die dann umdefinieren:





oder ohne die Hilfsvariable vielleicht:

?
Reksilat Auf diesen Beitrag antworten »

Ne, so bekommst Du ja nur Wörter, die auf b enden!

Wie siehts denn mit aus?

Bin weg!
prinzschleifer Auf diesen Beitrag antworten »

Gut, also hab ein bisschen weiter gearbeitet und bin auf folgende Inklusion gekommen, leider weiß ich nicht was ich induktiv beweisen soll ^^




Da ja gilt:

und





So jetzt hab ich einfach klug ersetzt:





So, und jetzt weiß ich nicht was ich Induktivbeweisen soll? Normalerweise macht man das über eine Aussage A(n), die hier wohlmöglich die obere Zeile ist, obwohl das ja einfach nur aus der Aufgabenstellung abgeschrieben ist. So jetzt muss ich was über die Anzahls der b's sagen.

Ich blicks einfach nicht.
prinzschleifer Auf diesen Beitrag antworten »

So, noch mal zur Formel:


Dieses Sternchen, also ich mein das bei bedeutet doch, dass ich diesen Term belieb mal hoch nehmen kann, wenn ich den nun ersetzen würde, durch dass n der rechten Gleichung wären diese doch fast identisch, also:




und es wäre eine legale Umformung, da ja n immer eine natürliche Zahl ist.

Bin ich auf dem richtigen Weg?
Reksilat Auf diesen Beitrag antworten »

Mensch schau Dir dich an was ich schreibe. Die Klammern stehen nicht ohne Grund da! Von zu sprechen ergibt außerhalb des Produkts keinerlei Sinn!

Es ist
So kannst Du jedes Wort darstellen, denn am Anfang stehen r_1 a's, dann kommt ein b, dann wieder r_2 a's und ein b. Am Ende nochmal s a's.
Beispiel:
w=aabbba, dann ist
w=aa, dann ist (Produkt über null Faktoren ergibt das leere Wort)
prinzschleifer Auf diesen Beitrag antworten »

Gut, jetzt hab ich's glaub ich verstanden smile

Hab das Produktzeichen halt noch nie in diesem Kontext gesehen verwirrt
Nunja, jetzt weiß ich bescheid.

So also ich muss folgendes Zeigen



Laut Vorraussetzung, soll b mindestens einmal drin vorkommen, dazu muss ich dann n auf mindestens 1 setzen, also



oder



richtig soweit?

Jetzt fängt der Induktionsspaß an, also wenn ich nun n inkrementiere sollte es immer noch drin liegen, und das muss ich zeigen oder?
Reksilat Auf diesen Beitrag antworten »

Zitat:

So also ich muss folgendes Zeigen



Das bestimmt nicht, denn das ist ja falsch (links liegt z.B. das wort a nicht drin)
Zitat:



Das ist zu zeigen, ja.
IA: Nimm ein Wort mit n=1, also und zeige, dass es in L liegt.
IS: Für ein liegen alle Wörter der Form in L. Zeige, dass dann auch alle in L liegen.

Irgendwie alles nicht so berauschend, eigentlich ist die Aufgabenstellung fast leichter zu sehen, als die obige Darstellung für , denn da muss man dann auch noch ein wenig dazuschreiben. Alles nicht so wichtig, hauptsache man lernt ein wenig mit Alphabeten und Wörtern zu arbeiten.
smile
prinzschleifer Auf diesen Beitrag antworten »

Ja, ich glaub das ist auch Sinn der Aufgabe smile

Induktionanfang ist recht einfach, da muss man ja einfach w dem A irgendwie zuordenen, also in L wäre dann:
recht trivial.


mit den obigen Vorraussetzungen.


Wie zeig ich hier das es in L liegt. Ich kann ja nicht einfach ein n wählen und zeigen dass es da drin liegt oder? Für mich ist das recht offensichtlich, aber wie man das eben zeigt.

n =1






Oder wie zeig das allgemein. Bestimmt ist es viel einfach als ich es mir vorstelle.
Reksilat Auf diesen Beitrag antworten »

Zitat:



Ist Dir der Sinn des Produktzeichens geläufig? In diesem Wort würden ja insgesamt 2n b's stecken!

Zitat:





Unfug! Was soll das i im zweiten Ausdruck sein? i ist ein Laufindex, der ohne das große Produktzeichen überhaupt keinen Sinn ergibt.

Es ist
Der erste Faktor ist per IV in L, der zweite liegt offensichtlich ebenfalls in L und dann sieht man ja auch, dass das Produkt zweier Vektoren aus L ebenfalls wieder in L liegt.
prinzschleifer Auf diesen Beitrag antworten »

Vielen, vielen dank.

Bin glaub ich auch noch zusehr darauf fixiert, dass ganze Mathematisch zu sehn und Distributivgesetze anzuweden usw.

Meine letzte Frage des heutigen Abends:

Es sei A = {a,b}. Beschreiben Sie unter Benutzung nur der Symbole {,}, a, b , *, + , (,) und Komma die folgende formale Sprache:

Die Menge aller Wörter über A, in denen nicht das Teilwort baa vorkommt.

Gut!

Also ich darf eigentlich nur unterbinden, dass es ein baa geben kann. Dazu hab ich mir folgendes überlegt:



Bin ich ganz weit weg, oder nah dran ^^

Vielen Dank für deine und eure Hilfe!
prinzschleifer Auf diesen Beitrag antworten »

Das was oben steht ist Unfug.

Also Regel Nummer 1 die gelten muss ist dass nach einem ba immer in b kommen muss.
Hab aber keine Ahnung wie ich das implementieren kann. Ich muss aber mit einem + arbeiten.

Also hier bin ich grade:



Dadurch wär aber aaaaaaaaaaaaaaba nicht darstellbar. mhhhh.




Dann könnte man aber das ganze kontaneieren:

was wieder verboten ist.

unglücklich

Edit: So mir fällt einfach nix mehr ein, du kannst!
Reksilat Auf diesen Beitrag antworten »

Ich warte noch... sag bescheid, wenn Du fertig bist Wink

Edit:
1. Das Wort kann mit beliebig vielen a's anfangen:->
2. Irgendwann taucht das erste b auf, dem jetzt beliebig viele weitere b's folgen können.->
3. Als nächstes kommt ein(!) a ->
4. Jetzt kommen wieder beliebig viele b's, d.h. wir sind wieder bei Punkt 2+3. Diese beiden Punkte können also beliebig oft wiederholt werden. Das musst Du jetzt noch formal ausdrücken.
5. Da unser Wort nicht auf a aufhören muss, können am Ende nochmal lauter b's stehen ->

Versuch's mal zusammenzubasteln. smile
prinzschleifer Auf diesen Beitrag antworten »

Tadadadda:




Kann sowas den nicht zu Problemen führen:

also solche Wörter kann man dann erstellen:




Denn wenn ich diese konkatiere kommt ja ein Wort raus das Verboten ist und genau das haben wir doch in der allerersten Aufgabe im Thread benutzt wo wir schauen mussten ob ein Wort in liegt.

Glaub ich habs: Die Frage war ja ob sie in enhalten sind und nicht in L. Ist das des Pudels Kern?

Oder habe ich da was falsch verstanden?
Reksilat Auf diesen Beitrag antworten »

Zitat:
Original von prinzschleifer
Tadadadda:



Die Klammer sitzt falsch! lies Punkt 4 nochmal genau durch!
prinzschleifer Auf diesen Beitrag antworten »

Ah:



So?
Reksilat Auf diesen Beitrag antworten »

Tadadadda! http://ugly.plzdiekthxbye.net/small/s226.gif

Gute Nacht!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »