Informatiker Board | Druckvorschau: typ 3 chomsky algorithmus

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
--- typ 3 chomsky algorithmus (http://www.informatikerboard.de/board/thread.php?threadid=289)

Geschrieben von info_jüdy am 27.10.2007 um 12:22:

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.

Geschrieben von kiste am 27.10.2007 um 16:47:

und was soll der algorithmus machen?

Geschrieben von info_jüdy am 28.10.2007 um 11:40:

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.

Geschrieben von Tobias am 28.10.2007 um 11:58:

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.

Geschrieben von info_jüdy am 28.10.2007 um 21:15:

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

Geschrieben von Tobias am 28.10.2007 um 22:27:

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.

}