Fachrat Informatik - Forum

Nein.

Demonstration:
S
A
a

Oder:

S
A
aA
aaA
aaa

Ich habe demonstriert, dass man mit deiner Grammatik auch Wörter erstellen kann, die eine ungerade Anzahl an a enthält.

kann mal jemand die lösung die in der übung gemacht worden ist für die beiden grammatiken hierreinposten!!!

Ich bin zwar aus der Materie schon etwas raus, aber eine Grammatik, mittels der man Wörter mit einer geraden Anzahl an a erzeugen kann, darf keine Wörter mit einer ungeraden Anzahl an a erzeugen können.
Sonst wäre die Übung witzlos.

gibts eigentlich irgendwelche tips und tricks wie man auf diese Produktionen kommt? Also irgendwie ein Standardweg, der einem immer irgendwie wenigstens ein bisschen hilft um zum ziel zu kommen?

Quoted

Original von ap
Ich bin zwar aus der Materie schon etwas raus, aber eine Grammatik, mittels der man Wörter mit einer geraden Anzahl an a erzeugen kann, darf keine Wörter mit einer ungeraden Anzahl an a erzeugen können.

Richtig. Etwas allgemeiner:

Eine Sprache (nennen wir sie L) kann man auf verschiedene Weisen definieren. Hier eine Auswahl:

1. wie in der Mathematik üblich als Menge
   
   Beispiel:
   L := {w aus {a, b}^* | |w|_a ist gerade}
   
   
2. mittels einer die Sprache L erzeugenden Grammatik G – jedes aus der Grammatik ableitbare Wort gehört dann zu L
   
   Beispiel:
   G := ({S, A, X}, {a, b}, P, S) mit P = {S -> epsilon, S -> X, X -> aA, X -> b, X -> bX, A -> aX, A -> bA, A -> a}
   
   
3. durch die Angabe einer Maschine
   
   Beispiel:
   passender endlicher Automat, Kellerautomat oder passende Turing-Maschine
   [/list=1]

Quoted

Original von Ernestinum[xic]
gibts eigentlich irgendwelche tips und tricks wie man auf diese Produktionen kommt? Also irgendwie ein Standardweg, der einem immer irgendwie wenigstens ein bisschen hilft um zum ziel zu kommen?

Das Zauberwort heißt hier leider (wie so oft in der Mathematik) Erfahrung.

Meistens findet man recht schnell einen Weg, wie man eine Sprache durch eine Grammatik beschreiben kann. Das Problem ist dann aber, diese Idee in eine konkrete Grammatik umzusetzen.

Im Fall der geposteten Lösung zu Aufgabe 1.2a kann man der in einer Ableitung auftretenden Variablen (also S, X oder A) gewisse Eigenschaften des bisher abgeleiteten Wortes zuordnen:

S: Start (Anzahl "a" = 0, Anzahl "b" = 0)
X: Anzahl "a" ist gerade
A: Anzahl "a" ist ungerade, es muß also noch (mindestens) ein "a" hinzugefügt werden

Das Prinzip (also daß man sich irgendwie merken muß, ob bisher eine gerade oder ungerade Anzahl "a"s abgeleitet wurde) ist einfach und mit ein wenig Übung ist es die Konstruktion der Grammatik auch.


Hier zur Übung noch ein paar Aufgaben zu regulären Grammatiken:

L1 := {w aus {0, 1, 2}^* | |w|_1 ist durch 3 teilbar}
L2 := {w aus {w, x, y, z}^* | w enthält irgendwo drei "x" in Folge}
L3 := {w aus {0, 1}^* | w beginnt mit "1"}
L4 := {w aus {0}^* | |w| ist eine Potenz von 2}
L5 := {w aus {a, b, c, d}^+ | |w| ist gerade}


Zu L2 gehören z. B. die Wörter "zzwwxxx", "xwxwxwxxxzzy" und "xxx".
Zu L4 gehören z. B. die Wörter "00", "0000" und "00000000".

Man gebe für jede dieser Sprachen eine reguläre Grammatik an (sofern möglich). Falls eine solche Grammatik nicht existiert, begründe man, wieso das so ist.

Quoted

Original von Uprooter
noch eine frage: dürfen bei einem DEA 2 übergäbge von 2 verschiedenen zuständen, zB das lesen von jeweils einem a, auf einen einzigen zustand hinführen?
ist es bei einem DEA erlaubt, dass ein zustand immer wieder auf sich zeigt, zb durch lesen von einem b und gleichzeitig auch noch einen übergang, auch durch lesen von einem b, zu einem andern zustand hat oder ist das schon ein NEA?

DEA: Von jedem Zustand aus muß für jedes Zeichen aus dem Alphabet genau ein Zustandsübergang existieren.

NEA: Es können beliebig viele Zustandsübergänge pro Zeichen aus dem Alphabet existieren.

Quoted

Original von Uprooter
oh man, fragen über fragen:
sind denn bei einer gramm prudktionen erlaubt, die zu einem wort führen, das überhaupt keine a's besitzt, wenn aber die sprache wörter mit zB einer geraden anzahl vons a's erzeugen soll?

Ist Null eine gerade Zahl?

Definition der Teilbarkeit: Eine ganze Zahl b aus Z heißt in Z durch eine ganze Zahl a aus Z teilbar, falls es eine ganze Zahl q aus Z gibt, so daß gilt q * a = b. Man schreibt dann a|b, gesprochen "a teilt b".

Somit ist die Null durch jede ganze Zahl teilbar, insbesondere durch die Zwei.

hab da eine frage zur sprache :L1 := {w aus {0, 1, 2}^* | |w|_1 ist durch 3 teilbar}


würde die foplgende grammatik gehen? (hab das thema noch nicht so wirklich durchblickt):

S->A
S->B
S->C
S->eps

A->0A
A->0B
A->0C
A->0

B->1D
D->1E
E->1
E->1B
E->1A
E->1c


C->2C
C->2B
C->2A
C->2
...sieht irgendwie voll umständlich aus oder?!

Quoted

Original von UGN
hab da eine frage zur sprache :L1 := {w aus {0, 1, 2}^* | |w|_1 ist durch 3 teilbar}


würde die foplgende grammatik gehen? (hab das thema noch nicht so wirklich durchblickt):

S->A
S->B
S->C
S->eps

A->0A
A->0B
A->0C
A->0

B->1D
D->1E
E->1
E->1B
E->1A
E->1c


C->2C
C->2B
C->2A
C->2
...sieht irgendwie voll umständlich aus oder?!

Sieht schon ganz gut aus, ist aber leider nicht ganz korrekt. Das Wort "01011" kannst du z. B. nicht ableiten, obwohl es zur Sprache L1 gehört.


Du verwendest außerdem unnötig viele Variablen. Es reichen drei Variablen aus:

• eine für "Anzahl '0' ist durch 3 teilbar"
  
• eine für "Anzahl '0' ist nicht durch 3 teilbar, es fehlt mindestens zweimal '0'"
  
• eine für "Anzahl '0' ist nicht durch 3 teilbar, es fehlt mindestens einmal '0'"
  

Im Prinzip funktioniert das genauso wie in der bereits in diesem Thread besprochenen Aufgabe (siehe meine Erklärung oben).