You are not logged in.

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

1

Thursday, February 12th 2004, 7:30pm

klausurvorbereitungen theoinf

hab mal eine frage gleich zum ersteb übungsbaltt, aufg 2 war eine typ-3-gramm zu erstellen, die wörter mit einer geraden anzahl an a's aus dem alphabet {a,b}* erstellt:
in der übung zu dieser aufgabe wurde eine lösung mit 2 variablen vorgeführt, würde auch diese lösung richtig sein?:
S->A
S->epsilon
A->aA
A->bA
A->b
A->a

ap

Erfahrener Schreiberling

Posts: 269

Date of registration: Feb 14th 2002

Occupation: Student ;-)

2

Thursday, February 12th 2004, 7:34pm

RE: klausurvorbereitungen theoinf

Nein.

Demonstration:
S
A
a

Oder:

S
A
aA
aaA
aaa
Who the fuck is General Failure and why does he read my hard disk? ?(

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

3

Thursday, February 12th 2004, 7:48pm

hm? ich versteh nicht was du meinst? kannst du es bitte etwas erklären?

ap

Erfahrener Schreiberling

Posts: 269

Date of registration: Feb 14th 2002

Occupation: Student ;-)

4

Thursday, February 12th 2004, 8:02pm

Ich habe demonstriert, dass man mit deiner Grammatik auch Wörter erstellen kann, die eine ungerade Anzahl an a enthält.
Who the fuck is General Failure and why does he read my hard disk? ?(

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

5

Thursday, February 12th 2004, 8:04pm

ja, aber eine gramm ist doch nciht eindeutig, wenn nur eine produktion zur lösung, also zum gesuchten wort, führt, dann stimmt die gramm oder hab ich da was falsch verstanden`?

  • "Ernestinum[xic]" is male

Posts: 83

Date of registration: Oct 15th 2003

Location: Hannover

Occupation: finde ich interessant!

6

Thursday, February 12th 2004, 8:06pm

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

ap

Erfahrener Schreiberling

Posts: 269

Date of registration: Feb 14th 2002

Occupation: Student ;-)

7

Thursday, February 12th 2004, 8:07pm

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.
Who the fuck is General Failure and why does he read my hard disk? ?(

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

8

Thursday, February 12th 2004, 8:12pm

oh, versteh, danke sehr, jetzt schnall ich erst wo der hacken an der sache ist :rolleyes:

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

9

Thursday, February 12th 2004, 8:15pm

also, für erste gramm:
S->epsilon
S->X
X->aA
X->b
X->bX
A->aX
A->bA
A->a

für zweite:
S->epsilon
S->abc
abc->abcabc
ab->ba
ba->ab
ac->ca
ca->ac
cb->bc
bc->cb

  • "Ernestinum[xic]" is male

Posts: 83

Date of registration: Oct 15th 2003

Location: Hannover

Occupation: finde ich interessant!

10

Thursday, February 12th 2004, 10:48pm

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?

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

11

Thursday, February 12th 2004, 11:12pm

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]
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

12

Thursday, February 12th 2004, 11:26pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 12th 2004, 11:32pm)


Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

13

Friday, February 13th 2004, 12:32pm

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?

This post has been edited 3 times, last edit by "Uprooter" (Feb 13th 2004, 12:36pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

14

Friday, February 13th 2004, 12:45pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Feb 13th 2004, 1:19pm)


Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

15

Friday, February 13th 2004, 1:14pm

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?

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

16

Friday, February 13th 2004, 1:22pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

17

Friday, February 13th 2004, 1:25pm

hab ich mir auchc so erklärt, wusste nur nicht genau obs hier auch zieht 8) dank dir

UGN

Praktikant

  • "UGN" is male

Posts: 29

Date of registration: Feb 14th 2004

18

Saturday, February 14th 2004, 10:16am

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?!

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

19

Saturday, February 14th 2004, 5:59pm

zu L2:
das wort muss min 1 mal 3 x'e in folge enthalten richtig? also können es an einer stelle auch mehr als 3 in folge sein, wenn es denn irgendwo trotzdem genau 3 gibt?
ist diese gramm dann korrekt?:
S->A, S->C
A->xB
B->xD
D->x, D->xE
C->zC,xC,wC,yC,S
E->zE,xE,yE,wE,w,x,z,y

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

20

Saturday, February 14th 2004, 6:03pm

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).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962