Formale Sprachen

[Conny]

Hi!

Ich muss zur nächsten Präsenz ein paar Aufgaben lösen. Ich muss sie nicht abgeben, wohl aber erklären können. Das wäre dann Prüfungsvorleistung.

Der Einfachheithalber hab ich die drei Seiten in einer PDF zusammengefügt. Falls das nicht okay ist, kann ich gern JPGs draus machen.

So, aber nun zum Eigentlichen:

---

Auf Seite 1 konnte ich Aufgabe 1.1.a) lösen. Die ist aber auch recht einfach, immerhin muss ich nur alle Wörter aufschreiben, deren Länge kleiner-gleich 2 ist.
Aufgabe 1.1.b) hab ich auch hinbekommen. Es sind 511 Sprachen.
Danach hat aber alles ausgehakt.

Wie mache ich 1.1.c)?
Eine unendliche Sprache ist eine Sprache mit unendlich vielen Wörtern, richtig? Wie soll ich die Sprache bzw. drei Sprachen dieser Art denn definieren? L = { a, b, c, aa, ab, ac, …} wäre doch keine richtige Definition. Und falls doch, würden mir trotzdem noch zwei Sprachen fehlen, um die Aufgabe zu lösen.

Für Aufgabe 1.2 bräuchte ich nur die ersten 3 Elemente von den beiden definierten Sprachen, damit ich einen Anhaltspunkt habe, wie ich das lösen kann.
Wäre das bei L1 = { €, 0, 00, …} und bei L2 = { €, 1, 11, …}?

Bei Aufgabe 1.3.a): Kann man sich da wild eine eigene lineare Ordnung zusammenbasteln? Oder gibt es da Richtlinien?

Kann mir zu 1.3.c) noch Jemand erklären, wie ich die Sprachdefinition lese? So richtig konnte mir Wikipedia da nicht weiterhelfen.

Aufgabe 1.4.a) wäre eine unendliche Sprache?

Aufgabe 1.4.b) hier wieder das Leseproblem mit den Definitionen.

Aufgabe 1.4.c) Unendlich viele Worte?

---

Die Seiten 2 und 3 hab ich dann doch noch allein auf die Reihe bekommen. Aber Seite 1 leider nicht. Hier die PDF:

Danke schonmal für eure Mühe.

[cmrudolph]

[QUOTE=Conny]Wie mache ich 1.1.c)?
Eine unendliche Sprache ist eine Sprache mit unendlich vielen Wörtern, richtig? Wie soll ich die Sprache bzw. drei Sprachen dieser Art denn definieren? L = { a, b, c, aa, ab, ac, …} wäre doch keine richtige Definition. Und falls doch, würden mir trotzdem noch zwei Sprachen fehlen, um die Aufgabe zu lösen.[/quote]
Das macht dir die Aufgabe 1.2 doch vor:
[tex]L_1 = \left{ a^i | i \in \mathbb{N}_0\right}[/tex]
Da fallen dir sicherlich noch 2 weitere ein

[QUOTE=Conny;68940]Für Aufgabe 1.2 bräuchte ich nur die ersten 3 Elemente von den beiden definierten Sprachen, damit ich einen Anhaltspunkt habe, wie ich das lösen kann.
Wäre das bei L1 = { €, 0, 00, …} und bei L2 = { €, 1, 11, …}?[/quote]
Mit deiner Annahme liegst du ganz richtig.
Die Aufgaben sind dann eigentlich ziemlich einfach. Wenn du zu einer noch Hilfe brauchst, einfach nochmal melden.

@Conny;68940

Bei Aufgabe 1.3.a): Kann man sich da wild eine eigene lineare Ordnung zusammenbasteln? Oder gibt es da Richtlinien?

Da gibt es keine sinnvolle lineare Ordnung. Also kannst du dir einfach eine ausdenken.

@Conny;68940

Kann mir zu 1.3.c) noch Jemand erklären, wie ich die Sprachdefinition lese? So richtig konnte mir Wikipedia da nicht weiterhelfen.

Zu deutsch: "Welche Wörter gehören zur Sprache L, die aus den Worten w besteht, für die gilt, dass w aus dem leeren Wort sowie den ein und zweistelligen Worten, die sich aus dem Alphabet erzeugen lassen, wobei gilt, dass [tex]w = w^R[/tex]. (Keine Gewähr, das ist bei mir schon etwas her…) Mit dem [tex]w^R[/tex] kann ich momentan nichts anfangen, weil R nicht definiert und mir nicht (mehr?) geläufig ist.

@Conny;68940

Aufgabe 1.4.a) wäre eine unendliche Sprache?

Da bin ich mir nicht ganz sicher, wie die Definition „unendliche Sprache“ aussieht. Zumindest kannst du die Wörter zählen, die jeweils enthalten sind (Sollte [tex]\left| \Sigma \right|^m[/tex] sein).

@Conny;68940

Aufgabe 1.4.b) hier wieder das Leseproblem mit den Definitionen.

Die Sprache enthält alle Wörter der Länge 0 bis m, die aus dem Alphabet gebildet werden können. Das sind ein paar mehr als bei 1.4.a: [tex]\sum\limits_{i=0}^m\left| \Sigma \right|^i[/tex] die geschlossene Darstellung weiß ich grad nicht.

@Conny;68940

Aufgabe 1.4.c) Unendlich viele Worte?

Ja.

[Conny]

[QUOTE=cmrudolph]Das macht dir die Aufgabe 1.2 doch vor:
[tex]L_1 = \left{ a^i | i \in \mathbb{N}_0\right}[/tex]
Da fallen dir sicherlich noch 2 weitere ein ;-)[/QUOTE]
Also, wenn ich jetzt statt a ein b oder ein c eintrage, wäre das genauso legitim? Könnte ich statt der natürlichen Zahlen auch die rationalen und die reellen Zahlen nehmen? Die wären ja auch beide unendlich.

@cmrudolph;69001

Zu deutsch: "Welche Wörter gehören zur Sprache L, die aus den Worten w besteht, für die gilt, dass w aus dem leeren Wort sowie den ein und zweistelligen Worten, die sich aus dem Alphabet erzeugen lassen, wobei gilt, dass [tex]w = w^R[/tex]. (Keine Gewähr, das ist bei mir schon etwas her…) Mit dem [tex]w^R[/tex] kann ich momentan nichts anfangen, weil R nicht definiert und mir nicht (mehr?) geläufig ist.

Heißt, dass ich alle Wörter aufschreiben soll, die maximal zwei Stellen haben und aus dem Alphabet {$, %, &} bestehen? Und das leere Wort wäre mit dabei? Also, dieses kleine komische €?

@cmrudolph;69001

Da bin ich mir nicht ganz sicher, wie die Definition „unendliche Sprache“ aussieht. Zumindest kannst du die Wörter zählen, die jeweils enthalten sind (Sollte [tex]\left| \Sigma \right|^m[/tex] sein).

Laut Skript ist eine unendliche Sprache eine Sprache mit unendlich vielen Wörtern. Und wenn m Element der natürlichen Zahlen + 0 ist, müssten die Wörter eine Länge von m Zeichen haben dürfen. Also, dachte ich, dass die Wörter unendlich lang sein dürfen, das Alphabet enthält auch unendlich viele Zeichen… So ganz ohne Begrenzung hätte ich die Sprache jetzt als unendlich eingestuft. Kann man die Wörter dann trotzdem zählen? Versteh ich m und n falsch?
Mir kam gerade noch ein anderer Gedanke: Wenn m z.B. 3 wäre, würde das bedeuten, dass wirklich alle Wörter exakt 3 Zeichen lang sein müssten? Bei einer Zeichenlänge von 3 würde das bei z.B. n=5 Zeichen dann 10 mögliche Wörter machen. Aber wie rechne ich das aus? Also, welche Formel gibt es dafür?

@cmrudolph;69001

Die Sprache enthält alle Wörter der Länge 0 bis m, die aus dem Alphabet gebildet werden können. Das sind ein paar mehr als bei 1.4.a: [tex]\sum\limits_{i=0}^m\left| \Sigma \right|^i[/tex] die geschlossene Darstellung weiß ich grad nicht.

Und um nochmal m=3 und n=5 aufzugreifen, dann wäre für diese Aufgabe die Lösung 26. Bleibt wieder die Frage, wo man für sowas die Formeln herbekommt? Bleibt mir da nichts Anderes übrig als selber was zu entwickeln?

Für den Rest sag ich schlichtweg danke.

[cmrudolph]

@Conny

Also, wenn ich jetzt statt a ein b oder ein c eintrage, wäre das genauso legitim?

Das mit b oder c meinte ich. Du kannst auch beliebig variieren. Beispielsweise [tex]ab^i[/tex] oder wie auch immer.

@Conny;69028

Könnte ich statt der natürlichen Zahlen auch die rationalen und die reellen Zahlen nehmen? Die wären ja auch beide unendlich.

Wenn du dir nochmal überlegst, was das „hoch i“ bedeutet, sollte dir schnell klar werden, dass das nicht geht. Du kannst schwerlich eine „krumme“ Anzahl an Zeichen hintereinanter hängen - eine Anzahl ist natürlicherweise eine Natürliche Zahl

@Conny;69028

Heißt, dass ich alle Wörter aufschreiben soll, die maximal zwei Stellen haben und aus dem Alphabet {$, %, &} bestehen? Und das leere Wort wäre mit dabei? Also, dieses kleine komische €?

Nicht ganz. Von den von dir genannten Wörtern musst du nur diejenigen aufschreiben, die die zweite Bedingung erfüllen. Ich weiß leider nicht, was das „hoch R“ bedeutet, daher fehlt eine Bedingung. Dem Aufgabenaufbau nach wird das etwas mit der linearen Ordnung zu tun haben. Dieses kleine komische € heißt übrigens Epsilon.

[QUOTE=Conny;69028]Laut Skript ist eine unendliche Sprache eine Sprache mit unendlich vielen Wörtern. Und wenn m Element der natürlichen Zahlen + 0 ist, müssten die Wörter eine Länge von m Zeichen haben dürfen. Also, dachte ich, dass die Wörter unendlich lang sein dürfen, das Alphabet enthält auch unendlich viele Zeichen… So ganz ohne Begrenzung hätte ich die Sprache jetzt als unendlich eingestuft. Kann man die Wörter dann trotzdem zählen? Versteh ich m und n falsch?
Mir kam gerade noch ein anderer Gedanke: Wenn m z.B. 3 wäre, würde das bedeuten, dass wirklich alle Wörter exakt 3 Zeichen lang sein müssten? Bei einer Zeichenlänge von 3 würde das bei z.B. n=5 Zeichen dann 10 mögliche Wörter machen. Aber wie rechne ich das aus? Also, welche Formel gibt es dafür?[/QUOTE]
Der Definition zufolge ist 1.4.a keine unendliche Sprache. Es gibt allerdings unendlich viele Sprachen, weil es unendlich viele m gibt. Wie viele Wörter die Sprachen jeweils enthalten, ist vom m abhängig - die Formel zur Berechnung habe ich im oberen Post geschrieben. Dabei hatte ich allerdings übersehen, dass [tex]\left| \Sigma \right| = n[/tex] gilt.
Das mit m=3 und n=5 haut nicht so ganz hin. Zumindest kann ich mir mehr als nur 10 dreistellige Wörter vorstellen, die man aus 5 Ziffern bilden kann. Wenn mich meine Kombinatorikkenntnisse nicht trügen, sind das [tex]n^m[/tex] (siehe oben) und das macht dann 125.

@Conny;69028

Und um nochmal m=3 und n=5 aufzugreifen, dann wäre für diese Aufgabe die Lösung 26. Bleibt wieder die Frage, wo man für sowas die Formeln herbekommt? Bleibt mir da nichts Anderes übrig als selber was zu entwickeln?

Da habe ich die Formel auch schon zu gepostet. [tex]\sum\limits_{i=0}^m\left| \Sigma \right|^i[/tex] bzw. [tex]\sum\limits_{i=0}^mn^i[/tex]. Eine geschlossene Form musst du dir dann aber selbst überlegen (gibt bestimmt eine) und dann per vollständiger Enumeration … ähm Induktion … beweisen.
Für m=3 und n=5 kommt dann 156 raus.

[Conny]

Okay, ich glaub ich bin fertig - fix und…

Die komplette 1.4. hat mich jetzt noch echt geschafft.
Für a) habe ich n^m notiert
Für b) habe ich “wenn n>^ -> L=n*((n^m-1)/(n-1))+1; wenn n=1 -> L = m+1” notiert. Die erste Formel ist eine hierfür angepasste Reihenformel für geometrische Zahlenfolgen und die zweite eine Notlösung, denn wenn n=1, dann Div/0.
Für c) hab ich ein Unendlich notiert.

Achso, die Sache mit dem w^R heißt, dass ich nur jene Worte in die Sprache aufnehmen darf, die ein Palindrom sind. Also, gespiegelte Worte. Explizit für diese Aufgabe ist dann die Lösung: {€, $, %, &, $$, %%, &&}

Ich sag auf jeden Fall nochmal danke. Ich hätte es ohne dich nicht hinbekommen.

[Crian]

Ich weiß nicht genau, wie eure Definitionen aussehen, aber selbst mit einem Buchstaben kann man doch unendlich viele Worte bilden: a, aa, aaa, aaaa, … ist das dann eine unendliche Sprache?

[cmrudolph]

Ja, siehe dazu auch in #2 die Definition von [tex]L_1[/tex]