Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female
  • "NullAhnung" started this thread

Posts: 332

Date of registration: Apr 28th 2003

1

Tuesday, May 18th 2004, 9:32pm

PuÜ Blatt 4

1. Hab ich das richtig verstanden: Ist First(X) die Menge aller Terminale, die auf X folgen können?
2. Wie ist das mit dem $ Zeichen? Kann das auch in einer Menge stehen in der auch andere Terminale stehen?
3. LL1-Bedingung: Bedeutet das, dass jedes Terminal in den Mengen nur einmal vorkommt? Also z.B. First(A)={*} First(B)={&,+}
  • Send private message

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

2

Wednesday, May 19th 2004, 10:15am

RE: PuÜ Blatt 4

Quoted

Original von NullAhnung
1. Hab ich das richtig verstanden: Ist First(X) die Menge aller Terminale, die auf X folgen können?


First(X) ist die Menge der Terminale, die bei den verschiedenen Produktionen aus dem Nicht-Terminal X an erster Stelle stehen können.
Follow(X) ist die Menge, die du meinst, alle Terminale und ggf. $, die auf das Nicht-Terminal folgen können.

Quoted

2. Wie ist das mit dem $ Zeichen? Kann das auch in einer Menge stehen in der auch andere Terminale stehen?


Natürlich bei den Follow Mengen, genau dann, wenn auf das Nicht-Terminal das Wortende folgen kann.

Quoted

3. LL1-Bedingung: Bedeutet das, dass jedes Terminal in den Mengen nur einmal vorkommt? Also z.B. First(A)={*} First(B)={&,+}


Die First Mengen "der rechten Seiten der Produktionen" müssen paarweise disjunkt sein, also eine leere Schnittmenge haben.
Weiter muss man die Followmenge des Nicht-Terminals mit berücksichtigen, wenn man aus ihm epsilon produzieren kann. Dann würde X "wegfallen" und das linkeste Zeichen an seiner Stelle ergibt sich aus den Zeichen der Follow Menge.

Es wird geprüft, ob die Wahl der Produktion bei einem gelesenen Zeichen eindeutig ist. Es dürfen also keine zwei Produktionsmöglichkeiten bestehen, bei denen an linkester Stelle das gleiche Zeichen auftaucht.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de

This post has been edited 2 times, last edit by "Informatik Minister" (May 19th 2004, 10:18am)

  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female
  • "NullAhnung" started this thread

Posts: 332

Date of registration: Apr 28th 2003

3

Friday, May 21st 2004, 5:26pm

Ist das schonmal richtig:

First(F) = {a, ( }
First(R) = {e, *}
First(A) = {e, +}
First(E) = {(, a} = First(D)

Follow(F) = *
Follow(E) = )
Follow(A) = $
Follow(R) = $
Follow(D) = +
  • Send private message

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

4

Friday, May 21st 2004, 6:04pm

Habe den Übungszettel nicht, aber ich vermute schwer, dass zu den FollowMENGEN noch mehr Elemente gehören.
Dort sind alle Terminale und evtl. $ enthalten, die bei beliebigen Produktionen hinter dem betreffenden Nicht-Terminal stehen können.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

5

Friday, May 21st 2004, 8:28pm

@Null Ahnung: Sowohl deine First als auch Follow Mengen sind falsch! Ein heißer Tipp!! Durch scharfes Hinsehen im Skript, hast du schon die Aufgabe 1!!! ;)
mfg
MAX

This post has been edited 3 times, last edit by "MAX" (May 21st 2004, 8:30pm)

  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female
  • "NullAhnung" started this thread

Posts: 332

Date of registration: Apr 28th 2003

6

Saturday, May 22nd 2004, 3:23pm

Versteh nicht warum die falsch sein sollen. First sind die die vor den Nichtterminalen stehen können und Follow die die dahinter stehen oder nicht?
Vielleicht kann das ja mal jemand erklären.
  • Send private message

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

7

Saturday, May 22nd 2004, 3:36pm

Quoted

Original von NullAhnung
Vielleicht kann das ja mal jemand erklären.


Der Informatik Minister hat's doch oben erklärt. :)
tar: Anlegen eines leeren Archivs wird feige verweigert.
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

8

Saturday, May 22nd 2004, 6:43pm

Quoted


Versteh nicht warum die falsch sein sollen. First sind die die vor den Nichtterminalen stehen können und Follow die die dahinter stehen oder nicht?
Vielleicht kann das ja mal jemand erklären.

Im Skript steht die beste Erklärung!!! Besser kann man es nicht erklären!!! Um noch deutlicher zu werden, schaue dir das Beispiel 2.38 im Skript genauer an!!!
mfg
MAX
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

9

Sunday, May 23rd 2004, 10:41pm

@MAX: Also entweder ich verpeil hier gerade ganz übel was (könnte auch gut sein, da ganzen Tag mitm Auto unterwegs) oder ich weiß nicht, aber ich hab die selben First-Mengen wie Null Ahnung raus, wo Du meintest, die wären falsch. Biste Dir da sicher?
Einzig in der Formulierung ist es ein bissi anders, aber sonst eigntl identisch.
Die Follow Mengen habe ich hingegen auch anders

Btw noch mal was aus Adminsicht. Laut Forenregeln solltet Ihr davon absehen Lösungen für Übungsaufgaben hier zu posten, insofern diese noch aktuell sind.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

10

Monday, May 24th 2004, 12:05pm

ups

Habe mich bei den First Mengen etwas verguckt. Sie sind tatsächlich richtig! Ich entschuldige mich dafür!
Zu Meiner Verteidigung: Ich habe zuerst ihre Mengen nicht genau angeschaut, sondern nur gezählt. Da es eigentlich nur drei unterschiedliche gibt und sie vier aufgeschrieben hat, obwohl zwei gleich sind, habe ich auch geschrieben, dass sie falsch sind. Es tut mir leid!!!
Die Follow Mengen von NullAhnung sind aber immer noch falsch!
mfg
MAX

This post has been edited 1 times, last edit by "MAX" (May 24th 2004, 12:06pm)

  • Send private message

mDev

Erfahrener Schreiberling

  • "mDev" is male

Posts: 282

Date of registration: Oct 10th 2002

Location: Hannover

Occupation: Wissenschaftlicher Mitarbeiter

11

Monday, May 24th 2004, 2:45pm

wie gehe ich denn bei First mit den terminalsymbolen um, die werden schliesslich nicht abgeleitet?

ist in aufgabe 1 zB First(+)=First(D) oder First(*)=First(F) ?

This post has been edited 1 times, last edit by "mDev" (May 24th 2004, 3:32pm)

  • Send private message

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

12

Monday, May 24th 2004, 3:37pm

Quoted

Original von mDev
wie gehe ich denn bei First mit den terminalsymbolen um, die werden schliesslich nicht abgeleitet?

ist in aufgabe 1 zB First(+)=First(D) oder First(*)=First(F) ?


FIRST(x) = x, wenn x ein Terminalzeichen ist.
Die stehen da und bleiben stehen, also können an ihrer Stelle auch nur sie selbst stehen, weil sie "terminal" sind...
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de
  • Send private message

MartinH

Zuhörer

  • "MartinH" is male

Posts: 1

Date of registration: May 23rd 2004

13

Monday, May 24th 2004, 5:20pm

Wie ist denn Aufgabe 2 gemeint? Also man nimmt eine neue Grammatik (zum Beispiel die Produktion von E abändern, die ja die LL1-Bed verletzt) und prüft dann ob die LL1 Bedingung jetzt nicht mehr verletzt wird? Wofür gibts denn dann 13 Punkte?
  • Send private message

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

14

Monday, May 24th 2004, 5:49pm

Quoted

Original von MartinH
Wie ist denn Aufgabe 2 gemeint? Also man nimmt eine neue Grammatik (zum Beispiel die Produktion von E abändern, die ja die LL1-Bed verletzt) und prüft dann ob die LL1 Bedingung jetzt nicht mehr verletzt wird? Wofür gibts denn dann 13 Punkte?


Achtgeben, dass die gegebene und die erzeugte Grammatik wirklich äquivalent sind, die Bedingung überprüfen und dann ist die Aufgabe fertig, wenn es eine ähnliche/die gleiche ist, wie vor einem Jahr.
"Fliegenpilze! Löwen!! Das Leben ist gefährlich." -- www.katzundgoldt.de
  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female
  • "NullAhnung" started this thread

Posts: 332

Date of registration: Apr 28th 2003

15

Monday, May 24th 2004, 7:18pm

Versuch ichs also nochmal mit diesen Mengen: Ich bin mir immer noch nicht sicher, ob ich das so richtig verstanden hab :(

Follow(E)= )
Follow(A)= $
Follow(R)= $, +
Follow(D)= +
Follow(F)= *, +, (
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

16

Monday, May 24th 2004, 7:44pm

Ist immer noch nicht richtig. Wende doch einfach den Algorithmus vom Skript Seite 48 oben an und zeichne den Follow-Graphen. Das geht viel einfacher.
Und bitte nicht immer Lösungen posten, da das Blatt ja noch abgegeben wird und sonst gegen die Forumsregeln verstöße.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female
  • "NullAhnung" started this thread

Posts: 332

Date of registration: Apr 28th 2003

17

Monday, May 24th 2004, 9:08pm

Dieser Algorithmus klappt bei mir auch nicht.
  • Send private message

MAX

Senior Schreiberling

  • "MAX" is male

Posts: 822

Date of registration: Dec 11th 2001

Location: Hannover

18

Monday, May 24th 2004, 9:14pm

Dann schaue dir das Beispiel 2.38 im Skript an! Dann hast du es! Ist es so schwer sich das anzuschauen?
mfg
MAX
  • Send private message