Aufgabe Spracharithmetik |
10.04.2008, 21:31 | Auf diesen Beitrag antworten » | ||
newsys | Aufgabe Spracharithmetik Hallo allerseits, ich habe eine Aufgabe und weiß nicht wie ich daran gehen soll. Wir haben erst 2 Vorlesungen gehört und der Prof ist nicht auf die Themen der Aufgaben eingegangen. Hier erstmal die Aufgabe: In dieser Aufgabe betrachten wir eine Unterfamilie von formalen Sprachen über einem Alphabet, die wir RA-Sprachen nennen wollen und die wie folgt definiert sind: • Die leere Menge ist eine RA-Sprache. • Die Menge {epsilon} für das leere Wort epsilon element Sigma* ist eine RA-Sprache. • Für jedes a element Sigma ist {a} eine RA-Sprache • Wenn R und S RA-Sprachen sind, so auch R u S, R ° S (auch RS geschrieben) und R* Nur die durch endliche Anwendung der obigen Regeln gebildeten Sprachen sind RASprachen. Gegeben sei das Alphabet {0, 1}. Zeigen Sie, dass folgende formale Sprachen über dem Alphabet Sigma ={0, 1} RA-Sprachen sind: 1. {epsilon, 0} 2. {w beginnt mit einer 1 und endet mit einer 0} 3. {w enthält eine gerade Anzahl an Nullen oder genau eine 1} 4. {w hat eine führende 1 und gerade Länge oder w hat eine führende 0 und ungerade Länge} Wie gehe ich an diese Aufgabe heran? |
||
|
|||
11.04.2008, 11:27 | Auf diesen Beitrag antworten » | ||
Tobias | Hallo, wenn ich es richtig überblicke, sind hier gerade die Regeln zur Bildung von Regulären Sprachen (RA = regulärer Ausduck?) angegeben. Du musst hier streng nach den formulierten Regeln deine Sprachmengen konstruieren. 1.) Ist ganz einfach und sollte dir eigentlich sofort gelingen. 2.) Das will ich einmal vormachen: Sei L = {w beginnt mit einer 1 und endet mit einer 0}. Wir wollen zeigen, dass . Dafür kann man L auch so schreiben: . Wir betrachten folgende Regeln: wegen wegen wegen und wegen wegen wegen
Willkommen an der Uni. |
||
12.04.2008, 12:39 | Auf diesen Beitrag antworten » | ||
newsys | ok das habe ich soweit verstanden. Aber ich habe noch Probleme mit der Anzahl. In Mathe würde ich jetzt einfach für eine gerade Anzal 2n nehmen und für eine ungerade 2n+1 aber wie mache ich hier. zB für die aufgabe {w enthält eine gerade Anzahl an Nullen oder genau eine 1} L = ???? v {1} |
||
12.04.2008, 13:46 | Auf diesen Beitrag antworten » | ||
Tobias | Der Trick ist jeweils die Menge so darzustellen, dass man die vorgegebenen Operatoren sofort erkennt. Ein "oder" in deiner Formulierung weist z.B. auf eine Vereinigung hin. Man kann also L = {w enthält eine gerade Anzahl an Nullen oder genau eine 1} so schreiben: X = {w enthält eine gerade Anzahl an Nullen } Y = {w enthält genau eine 1} Y ist recht einfach zu modellieren. Wie sehen alle Worte aus, die genau eine 1 enthalten? X ist etwas kniffliger. Eine Idee ist, jedes Wort aus X so aufzuteilen, dass jedes Teilwort GENAU zwei 0en enthält. Wenn man solche Teilwörter konkateniert, erhält man zwangsläufig ein Wort mit gerade vielen 0en. Man erhält also für die Teilwörter eine Menge . Konkateniert man beliebig viele Wörter aus T (also T*) hat man fast die Menge X. Was noch fehlt ist die Möglichkeit, dass X garkeine 0en (0 ist auch eine gerade Zahl) enthält. |
||
Anzeige | |||
|
|||
13.04.2008, 11:48 | Auf diesen Beitrag antworten » | ||
newsys | Ok - das sollte ich so hinbekommen. Schonmla vielen Dank. Jetzt habe ich noch eine Frage und zwar wie man an diese Aufgabe rangeht: Erstellen Sie für jede der folgenden Sprachen über dem Alphabet = {0, 1} eine kontextfreie Grammatik und begründen Sie informal, dass Ihre Grammatik tatsächlich die Sprache erzeugt. 1. {w ∈ | w enthält mindestens eine 1} 2. {w ∈ | w beginnt und endet mit demselben Symbol} Genauso wie an Aufgabe 1??????? Oder muss man da noch Produktionsregeln finden??? |
||
13.04.2008, 16:47 | Auf diesen Beitrag antworten » | ||
Tobias | Eine Grammatik besteht aus Terminalsymbolen, Nichtterminalsymbolen, Produktionsregeln, Startsymbol. Sowas sollst du finden. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|