Sprachtypen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Aufgabe 1: Grammatiken
Gegeben sei folgende Grammatik mit dem Startsymbol S:
N = {S, M, N, Z}
T = {a, b}
P = { 1. S = ’a’S;
2. S = ‘b’S;
3. S = ‘a’M;
4. M = ‘a’N;
5. N = ‘a’N;
6. N = ‘b’N;
7. N = ‘b’Z;
8. Z = ‘a’’a’; }
1. Welchen Typ hat die Grammatik bzgl. der Chomsky-Hierarchie?
3. Welchen Typ hat die durch die Grammatik definierte Sprache? |
Ich zebreche mir mein Kopf seit tagen wegen der Aufgabe.
Zu der ersten frage habe ich geschrieben:
Typ2 Kontextfrei weil auf der rechten Seite der Produktionsregels befinden sich nur Nichtterminalzeichen. Außerdem kann man auch Typ 3 regulär auschließen, weil man ja keine (unendlich) lange Sprache erzeugen kann wie z.b:
zaaaaaaa oder so.
Zu der dritten frage habe ich nichts geschrieben, weil hier schon wieder vom Typ geredet wird.
Meine frage ist nun worin unterscheiden sich die Aufgaben und ist meine Lösung zu 1 richtig?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:34 Di 02.11.2010 | | Autor: | felixf |
Moin!
> Aufgabe 1: Grammatiken
> Gegeben sei folgende Grammatik mit dem Startsymbol S:
> N = {S, M, N, Z}
> T = {a, b}
> P = { 1. S = ’a’S;
> 2. S = ‘b’S;
> 3. S = ‘a’M;
> 4. M = ‘a’N;
> 5. N = ‘a’N;
> 6. N = ‘b’N;
> 7. N = ‘b’Z;
> 8. Z = ‘a’’a’; }
>
> 1. Welchen Typ hat die Grammatik bzgl. der
> Chomsky-Hierarchie?
>
> 3. Welchen Typ hat die durch die Grammatik definierte
> Sprache?
>
> Ich zebreche mir mein Kopf seit tagen wegen der Aufgabe.
>
> Zu der ersten frage habe ich geschrieben:
> Typ2 Kontextfrei weil auf der rechten Seite der
> Produktionsregels befinden sich nur Nichtterminalzeichen.
Das stimmt doch gar nicht. a und b sind Terminale.
Kontextfrei ist es trotzdem.
Aber warum ist die Grammatik nicht regulaer?
> Außerdem kann man auch Typ 3 regulär auschließen, weil
> man ja keine (unendlich) lange Sprache erzeugen kann wie
> z.b:
> zaaaaaaa oder so.
Was hat das mit regulaeren Grammatiken zu tun!?
> Zu der dritten frage habe ich nichts geschrieben, weil hier
> schon wieder vom Typ geredet wird.
>
> Meine frage ist nun worin unterscheiden sich die Aufgaben
> und ist meine Lösung zu 1 richtig?
In der dritten Frage ist nach der von der Grammatik erzeugten Sprache gefragt. Nur weil du eine nicht-regulaere Grammatik hast, bedeutet das noch lange nicht, dass es nicht etwa auch eine regulaere Grammatik gibt, die dieselbe Sprache erzeugt.
Du musst schon genauer begruenden, warum die Sprache nicht leer ist (Stichwort: ![[]](/images/popup.gif) Pumping-Lemma) oder alternativ eine regulaere Grammatik angeben, die die Sprache erzeugt.
LG Felix
|
|
|
| |
|
Also wenn ich die Produktionsregel von 1.-7. betrachte sehe ich, dass es zunächst einmal Regulär ist. Doch die 8.Zeile ist ein Argument dafür, dass es eine kontextfreie Grammatik ist.
Meine Begründung:
Bei der Kontextfreien Grammatik ist die einzige Einschränkung, dass links vom => nur ein Nonterminal steht, rechts kann alles mögliche stehen.
Ist das Richtig?
Das könnte ich zu Aufgabe 1 schreiben.
Zu der Aufgabe 3.
könnte ich schreiben das es eine rechtslineare Sprache ist?
und würde dies genügen?
Bei meinen Lösungsunterlagen steht was von regulär das bringt mich durcheinander weil ich ja oben bei 1 davon ausgehe das es kontextfrei ist.
Oder eine ganz spezielle frage, wenn man mir die beantwort vielleicht komme ich ja dann selbständig zu der richtigen Lösung.
Wie ermittle ich den Typ der Grammatik?
Das war das was ich in Aufgabe 1 tat.
Wie ermittle ich den Typ der Sprache, die durch die Grammatik erzeugt wird?
Danke schonmal!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Do 04.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:21 Di 09.11.2010 | | Autor: | Shurakai |
Die Frage ist zwar schon abgelaufen, dennoch:
1.) Du argumentiertest zunächst, dass die Sprache nicht unendlich wäre. Dies ist offensichtlich falsch - wende beliebig oft die 1. Regel an. Außerdem sind auch endliche Sprachen insbesondere regulär, IMMER! (Die Inklusion ist sogar echt (wieso?))
2.) Die Sprache ist regulär. Du sagtest bereits, dass nur die letzte Regel A => aa stört. Wie kann man diese ersetzen, so dass die Sprache regulär ist, d.h. dass die letzte Regel die Form A => aB hat? (Ok ok, es ist offensichtlich, dass die (neue!) Regel für die (neue!) Variable B die Form B => a hat)
|
|
|
|
