sprache formell beschreiben < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 00:40 Fr 27.05.2011 | | Autor: | Blubie |
Ich habe diese Frage in keinem anderen Forum gestellt
Hallo, wir hatten letzte Woche die Themen Grammatik und Sprachen in der Vorlesung. Nun stellen sich mir eine Fragen:
1.) Worin liegt der Unterscheid ob ich beim Ableiten einen normalen oder einen Doppelpfeil nehme?
2.) Dann steht beim Doppelpfeil manchmal ein *, was bedeutet dieser Stern beim ableiten? Ein Stern bei einer Menge an Zeichen, also einem Alphabet, ist die Menge aller Zeichenketten, die mit diesem Alphabet dargestellt werden können, oder?
3.) Ist das Startsymbol eindeutig oder darf man auch mehrere Startsymbole definieren?
4.) Was ist der Unterschied zwischen einer Chomsky-Grammatik und einer normalen (formalen) Grammatik?
5.) Sowohl die Menge der Terminale als auch die Menge der nicht-Terminale ist ein Alphabet laut Definition, oder?
6.) Darf bei der Definition einer Grammatik auch eine rekursive Produktion mit dem Startsymbol beschrieben werden bzw. darf es öfter verwendet werden?
7.) Darf das Startsymbol ein terminal sein? also so, dass die Sprache L(G) nur ein Element hat bzw. darf das Startsymbol auch aus mehreren Zeichen bestehen?
8.) Müssen die Mengen der Produktionen, (Startsymbole?), Terminale und nicht-Terminale endlich sein?
9.) Es gilt ja laut Definition: Wörter sind Strings aus T* und Satzformen sind String aus (T [mm] \cup [/mm] N)* D.h. also Wörter sind auch Satzformen? Weiterhin ist die leere Zeichenreihe auch eine Satzform und ein Wort zugleich, oder?
10.) Zu den Chomsky-Hierarchie. Es heißt ja, dass jede typ-2 grammatik auch eine typ-1 grammatik ist. Jetzt habe ich aber gelesen, dass typ-2 grammatiken auch eine leere Folge produzieren dürfen. Dann wären aber links mehr Elemente als Rechts und somit wäre die typ-2 grammatik keine typ-1 grammatik mehr. Kann man den Widerspruch irgendwie aufklären?
11.) Existiert zu jeder Sprache eine Grammatik?
Weiterhin sollten wir folgende (Chomsky??)-Grammatik "informell" beschreiben:
T={a,b,c,d}, nicht-T={A,B}, Startsymbol ist A [mm] \in [/mm] nicht-T, P = {A -> Bc,B -> aBb,B -> d} (Hier stehen jetzt komischerweise wieder die einfachen Pfeile)
Intuitiv würde ich, wenn ich die Sprache informell beschreiben soll, einfach sagen, dass Folgendes gilt:
[mm] L(G)=\{a^n d b^n c | n>=0 \} [/mm] . Allerdings ist das ja nur eine "Vermutung" und Beweistechniken oder sonstiges in der Richtung hatten wir noch nicht. Reicht eine direkte Angabe?
Noch eine letzte Frage: In der Aufgabe hieß es, beschreibe die Sprache "informell". Gibt es unterschiede bei der Beschreibung einer Sprache oder wählt man immer diese Mengendartellung bzw. wieso extra dieses "informell".
Das sind viele kleine Fragen aber wenn ich darauf überall eine Antwort hätte, dann wüsste ich viel besser bescheid. Ich hoffe jemand kann mir helfen. Danke, danke, danke im Voraus!!!!!!!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 So 29.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:57 So 29.05.2011 | | Autor: | Blubie |
Kann mir niemand eine Antwort zu diesen Fragen geben? :(
|
|
|
|
