Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Einen Algorithmus schreiben
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Einen Algorithmus schreiben
 
Autor Nachricht
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 18 Jan 2009 - 10:05:45    Titel: Einen Algorithmus schreiben

Hallo,

ich möchte einen rekursiven Algorithmus schreiben, der aus einem reulären Ausdruck eine kontextfreie Grammatik erstellt.
Wie kann ich das bewerkstelligen?

Grüße

rumpi

Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 18 Jan 2009 - 13:43:36    Titel:

Wie generiert man denn aus einem regulären Ausdruck schrittweise einen NEA?
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 18 Jan 2009 - 18:28:10    Titel:

Ich habe hier einige reg Ausdrücke und die Neas dazu. Aber nicht wirklich nen Algorithmus, der einem die Umsetzung verständlich machen könnte :/

Edit: Hab es nun glaube verstanden.

Wenn man einen Automaten hat, nimmt man doch jeden Zustand als Variable für die Gramatik. Die Übergänge sind dann doch die Terminalsymbole.

Wenn ich jetzt also aus nem reg Ausdruck den NEAS Konstruiere und festelle, dass von einem Zustand q3 einen # nach q4 geht wäre die Produktion dafür:
q4 --> eps ?

Ich verstehe jetzt aber nicht, wie ich das schrittweise mit z.B.
(yy + x)∗ + (yy + x)∗ machen sollte?
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 18 Jan 2009 - 22:48:52    Titel:

Keiner ne Idee :/ ??
Stagger
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 01.08.2008
Beiträge: 7

BeitragVerfasst am: 18 Jan 2009 - 22:58:25    Titel:

Zitat:
Wenn ich jetzt also aus nem reg Ausdruck den NEAS Konstruiere und festelle, dass von einem Zustand q3 einen # nach q4 geht wäre die Produktion dafür:
q4 --> eps ?

Die Produktion für einen spontanen Übergang von q3 nach q4 ist doch
q3 --> q4

Zitat:
Ich verstehe jetzt aber nicht, wie ich das schrittweise mit z.B.
(yy + x)∗ + (yy + x)∗ machen sollte?

Tippfehler? Denn:
(yy + x)∗ + (yy + x)∗ = (yy + x)∗


Tipp zur Aufgabe:
Man hat r = 0* 1 (0 + 1)*. Dann wäre die Startregel:
S --> 0* 1 (0 + 1)*

Nun verwandelst du das Stück für Strück in Übergangsregeln einer kontextfreie Grammatik. Nächster Schritt wäre zum Beispiel:
S --> 0* 1 (T)*
T --> 0 | 1

usw.
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 18 Jan 2009 - 23:21:40    Titel:

Kann ich denn sowas machen, wie regeln für Vereinigung, Konkatenation, * und Klammerung ect aufstellen, die immer wieder angewandt werden müssen, bis keine dieser Symbole mehr Übergangsdiagramm sind?

Muss man dann ne While Schleife machen? Wie "korrekt" formuliert man denn sowas?
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Einen Algorithmus schreiben
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum