typ 3 chomsky algorithmus

27.10.2007, 12:22

info_jüdy

typ 3 chomsky algorithmus

ich bruache einen beispiel algorithmus für eine typ 3 grammatik. wäre super wenn mir da jemand weiter helfen könnte.

27.10.2007, 16:47

Auf diesen Beitrag antworten »

kiste

und was soll der algorithmus machen?

28.10.2007, 11:40

Auf diesen Beitrag antworten »

info_jüdy

eine typ 3 grammatik ausführen die einen tresorcode knackt. ich weiß allerdings nicht ob ich da schon die grammatik benutzen darf die ich bei einer aufbage weiter geschrieben habe, vermutlich eher weniger.

28.10.2007, 11:58

Auf diesen Beitrag antworten »

Tobias

Mir ist leider auch vollkommen unverständlich, was du willst.

Erstens: Eine Typ-3 Grammatik kann man nicht "ausführen". Es sind Produktionsregeln, die einen gewissen Aufbau haben müssen, damit die produzierte Sprache regulät (d.h. Typ-3) ist.

Für reguläre Sprachen benutzt man eigentlich viel lieber endliche Automaten.

Damit wir dir in irgendeiner Weise helfen können, musst du dich etwas klarer ausdrücken.

28.10.2007, 21:15

Auf diesen Beitrag antworten »

info_jüdy

In der Zwischenzeit ist es Ihre Aufgabe einen Algorithmus anzugeben, der f¨ur
eine beliebige Typ 3-Grammatik alle W¨orter der durch die Grammatik erzeugten
Sprache nacheinander ausgeben kann.
Hinweis: Nutzen Sie die spezielle Struktur von Typ 3-Grammatiken aus. Beachten
Sie auch, dass in der Grammatik mehrere Produktionen f¨ur eine Variable erlaubt
sind (zum Beispiel A ! a und A ! b).

dann halt doch die ganze aufgabe

28.10.2007, 22:27

Auf diesen Beitrag antworten »

Tobias

Das Ganze lässt sich z.B. rekursiv formulieren. Wir beginnen mit dem Startsymbol und leiten es auf alle Möglichkeiten ab. Das Ergebnis ist eine Satzform (ein Wort aus Terminalen und Nichtterminalen). Ist in der Satzform kein Nichtterminal mehr vorhanden, dann haben wir ein Wort der Sprache abgeleitet und geben es aus. Ansonsten nehmen wir das linkeste Nichtterminasymbol und leiten es auf alle möglichen Arten ab. Man kann alle möglichen Ableitungen als Ableitungsbaum ansehen und der Algorithmus traversiert diesen Baum.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Algo(Satzform X) {

  Falls X kein Nichtterminalsymbol hat:
     Gib X zurück
  Sonst
     X = a1a2..akAY // ai sind Terminalsymbole, A ist das erste Nichtterminalsymbol und Y ist Satzform
     
     Für jede Produktion der Form A --> Z tue: // Z ist Satzform
        Gib Algo(a1a2...akZY) zurück.

}

29.10.2007, 20:51

Auf diesen Beitrag antworten »

info_jüdy

vielen vielen dank!
ich habs zwar noch nicht ganz so alles verstanden aber den ansatz.

Neue Frage »

Antworten »

typ 3 chomsky algorithmus

Verwandte Themen