Chomsky-Hierarchie < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:03 So 04.05.2008 | | Autor: | mangaka |
Moin,
Ich habe am Mi meine mündliche Prüfung(Abitur) in Informatik.
Im Augenblick bin ich mit der formalen Sprache beschäftigt bzw. mit der Chomsky-Hierarchie.
Ich habe Probleme mit den Beschreibungen der Grammatiken.
Folgendes habe ich bisjetzt herausgefunden:
Typ 3 - reguläre Grammatik: Rechts des Terms darf nur eine Terminale oder eine Terminale gefolgt von einer Variable stehen(rechtsregulär)
// mit Term meine ich sowas: S->aV
Typ2 - kontextfreie Grammatik: Links darf nur eine Variable stehen, sonst gibt es keine Einschränkungen.
Ist das soweit richtig?
Kann jemand erklären, wie es mit den Einschränkungen bei der kontext-sensitiven Grammatik aussieht? Aber bitte in verständlicher weise ohne mathematischen Beschreibungen. Deswegen verstehe ich nämlich die Definitionen im Internet(Google) nicht.
Ich freue mich schon auf die Erleuchtung :)
Schönen Abend noch!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:26 Mo 05.05.2008 | | Autor: | Gilga |
Ist das soweit richtig? Ja. Zu bedenken ist, dass es viele äquivalente Definitionen gibt.
kontext-sensitiven Grammatik
rechte Seite der Regel muss mindestens so lange sein wie die linke. Das nennt man monoton.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:28 Mo 05.05.2008 | | Autor: | mangaka |
was heisst denn mindestens so lang?
bedeutet es, dass es links mindestens soviele terminale und variablen geben muss wie rechts? oder dass die terminale und variablen zusammengefasst als zeichen links mehr sein müssen als rechts?
der start muss sich nicht der bedingung beugen oder?
z.b. S->abCd ...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:02 Mo 05.05.2008 | | Autor: | mangaka |
konnte ich mich nicht richtig ausdrücken?
bitte um eine rückmeldung, falls ich es nicht konnte.
edit:hab versucht den post zu löschen...aber irgendwie geht das nicht^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:39 Di 06.05.2008 | | Autor: | Gilga |
Für alle Regeln v->w gilt: |v|<=|w|
Das wichtige ist die Entscheidbarkeit des Wortproblems.
Man baut den Ableitungsbaum so lange auf bis alle Terminalsequenzen min so groß sind wie das Wort.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 08.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:17 Di 06.05.2008 | | Autor: | mangaka |
ich hab gelesen, dass man angeben muss, wenn man die frage in einem anderen forum auch stellt.
ich habe dies soeben getan, weil ich nicht mehr viel zeit habe, um auf die antwort zu warten.
danke fuer die bisherige antwort!
forum:
http://abiunity.de/thread.php?sid=&postid=10714#post10714
|
|
|
| |
|
Erst einmal muss man sagen, dass das NICHT korrekt ist.
Für diese Hierarchie gilt nämlich, dass Typ 3 in Typ 2 in Typ 1 in Typ 0 enthalten ist.
D.h., dass Typ 3 auch die Bedingungen von Typ 2, Typ 1 erfüllen muss. (Typ 0 hat ja keine Bedingungen)
Sonst ist es aber in Ordnung.
Die Bedingung von Typ 0 sagt einfach aus, dass auf der linken Seite deiner Produktionsregel (deines "Terms", wie du es nanntest) weniger stehen darf als auf der rechten Seite, egal ob Variablen oder Terminalsymbole.
Also S->AB ist okay, aber AB->C ist verboten.
|
|
|
|
