0 Daumen
64 Aufrufe

Hallo,

Ich arbeite mich gerade in die formalen Sprachen ein und komme nicht drauf wie man eine Grammatik für eine Sprache findet. Habe mich gestern Abend sowie die letzten knapp 4 Stunden in die Materie eingearbeitet, soweit es mir möglich war. Ich verstehe die Grundbegriffe und verschieden Konzepte, doch hakt es bei mir, wie meistens bei solchen Dingen, wenn es an die wirkliche Ausführung der Aufgaben geht. 

Bild Mathematik

Möchte jetzt erstmal insbesondere Hilfe für die erste Aufgabe, die beiden anderen habe ich mir noch nicht angeschaut. Aber wenn mir jemand bei allen helfen mag, dann würde ich das auch gerne annehmen.

Ich die Grammatik rausfinden, nur eine bestimmte Anzahl an Nichtterminalen verwenden und ich muss ein enthaltenes Wort mit mindestens Wortlänge 5 finden sowie ein nichtenthaltenes mit derselben Länge. 

Eine Grammatik wird ja durch G = (V, E, P, S) definiert. 

V wäre ja, soweit ich weiß, die Nichtterminale S. Was mich jetzt aber auch verwirrt an der Aufgabenstellung ist die Sache mit "Maximale Anzahl der Nichtterminale". Soweit ich weiß könnte ich auch andere Buchstaben wie A oder B als Nichtterminale definieren, aber wie genau ich das hier machen soll, weiß ich nicht.

Habe an etwas wie 

S -> aS und S -> bS gedacht, aber ich glaube das wird wohl nicht stimmen.

Ich weiß auch nicht, wie genau ich für w einsetzen darf. Da ich ja eine Wortlänge von 5 oder mehr kreieren muss, muss ich ja mehr als nur das w durch ein Wort ersetzen. 

Bitte um Hilfe :(

Gefragt von

1 Antwort

0 Daumen

Du brauchst ja jedenfalls ein nichtterminales Startsymbol, etwa S.

Und um Wörter der Sprache zu erzeugen hast du ja nur zwei Möglichkeiten, entweder

ein a vor ein vorhandenes Wort und gleichzeitig eins hinten dran oder eben entsprechend mit b,

also sind deine Regeln    S ---> aSa      oder auch  S -----> bSb  und  S ----->  ε (leeres Wort)

und wenn du jetzt z.B. erst 2x   die 1. dann 1x  die 2. dann 1x  die 3. Regel anwendest, hast du

S ------>   aSa ----->   aaSaa   ------------->  baaSaab ---------->   baaaab

also schon mal ein Wort der Sprache.

Nicht in der Sprache ist etwa abbbb, weil es eben nicht gespiegelt sich selbst ergibt.

Manche Leute nennen das auch Palindrom. Sieh mal dort Sprache der Palindrome

https://de.wikipedia.org/wiki/Ableitung_%28Informatik%29

Beantwortet von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...