Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

EBFN Grammatik zu DFA
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> EBFN Grammatik zu DFA
 
Autor Nachricht
Kenaj
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 12.09.2006
Beiträge: 105

BeitragVerfasst am: 26 März 2010 - 17:37:42    Titel: EBFN Grammatik zu DFA

hallo zusammen,

ich muss follgende aufgabe lösen und stehe mir glaub selbst auf dem schlauch vieleicht kann mir jemand den richtigen weg weisen.
[img]http://yfrog.com/ehbildschirmfoto20100326up[/img]

wenn ich dies in eine reguläre gramatik ändere sieht dies so aus:

R->G
R->G.
R->G.N
R->G.N'E'G
G->N
G->VN
N->Z
N->ZN
Z->0
Z->1
.
.
.
Z->9
V->+
V->-

muss ich nun diese weiter vereinfachen z.b
G->Z
G->ZN
G->VZ
G->VZN

bis die nicht Terminale nur noch auf Terminale abgebildet werden?
auch komme ich nicht darauf was der Start wert sein soll.

meine Idee ist es zuerst einen NFA zu generieren und dann diesen zu einem DFA optimieren.

liege ich hier komplett auf dem Holzweg?

vielen dank schon im Voraus

lg Kenaj
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 26 März 2010 - 18:28:11    Titel:

Da nicht jede Grammatik linear ist, gibt es auch keine Algorithmus um aus einer beliebigen gegebenen Grammatik, welche die Sprache L generiert, einen endlichen Automaten aufzustellen, welcher die gleiche Sprache akzeptiert. Andersherum ist das natürlich kein Problem.
Kenaj
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 12.09.2006
Beiträge: 105

BeitragVerfasst am: 26 März 2010 - 21:08:52    Titel: sprich das bedeutet für mich?

danke für die antwort.

gibt es irrgentwelche ansätze dies zu lösen oder einfach "wild" drauf los überlegen?

lg

kenaj
kamischiki
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 10.12.2004
Beiträge: 129
Wohnort: Kiev/Frankfurt

BeitragVerfasst am: 26 März 2010 - 22:53:42    Titel:

also, wenn du die grammatik so hinkriegst, dass alle regeln die form A->a oder A->aB haben (gross sind die Variablen, klein die Terminalzeichen), dann ist es ganz einfach automaten zu bauen: Variablen sind zustände, für jedaes regel A->aB füge im automaten ein übergang ein (delta(A,a)=B).

aber wie gesagt, dafür muss grammatik in der richtigen form sein, viel spass dabei Smile
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> EBFN Grammatik zu DFA
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