Aufgabe Spracharithmetik |
newsys
Jungspund
Dabei seit: 04.11.2007
Beiträge: 15
|
|
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?
|
|
10.04.2008 21:31 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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
Zitat: |
Wir haben erst 2 Vorlesungen gehört und der Prof ist nicht auf die Themen der Aufgaben eingegangen. |
Willkommen an der Uni.
|
|
11.04.2008 11:27 |
|
|
newsys
Jungspund
Dabei seit: 04.11.2007
Beiträge: 15
|
|
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 12:39 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
12.04.2008 13:46 |
|
|
newsys
Jungspund
Dabei seit: 04.11.2007
Beiträge: 15
|
|
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 11:48 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Eine Grammatik besteht aus Terminalsymbolen, Nichtterminalsymbolen, Produktionsregeln, Startsymbol. Sowas sollst du finden.
|
|
13.04.2008 16:47 |
|
|
|