Chomsky-Hierarchy < Sonstiges < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:08 Mo 05.12.2011 | | Autor: | emulb |
| Aufgabe | Gegeben sei die folgende Grammatik G = (T,NT, P, S) mit
T = {(, ), n,+,* }
NT = {S, A,B}
P = {S := A | S + A,
A := B | A * B,
B := n | (S)
}
Entscheide ob Typ 1,2 oder Typ3. |
Typ 1 gilt nicht, weil die Worte auf der rechten Seite sind nicht mindestens so lang, wie die auf der linken Seite
und
Jetzt kann ich mich zwischen 2 und 3 nicht entscheiden bei Typ 2 steht hier ja eine Variable links alleine??
oder Typ 3, weil auf der rechten Seite sind entweder einzelne Terminalzeichen oder ein Terminalzeichen gefolgt von einer Variablen.
|
|
| |
|
Hallo emulb,
das ist sehr schlecht zu lesen, da werden so einige Zeichen komisch umgewandelt.
Was sollen die komischen Quadrate bedeuten mit 00,03 drin?
Wieso verwendest du nicht den Editor? Du bist doch nun schon lange genug dabei.
> Gegeben sei die folgende Grammatik G = (T,NT, P, S) mit
> T = {(, ), n,+,* }
> NT = {S, A,B}
> P = {S := A | S + A,
> A := B | A * B,
> B := n | (S)
> }
>
> Entscheide ob Typ 1,2 oder Typ3.
> Typ 1 gilt nicht, weil die Worte auf der rechten Seite
> sind nicht mindestens so lang, wie die auf der linken
> Seite
Hää? Auf der linken Seite sind sie alle von Länge 1, ist rechterhand irgendwo eines mit Länge 0?
Wohl nicht! Rechterhand hat alles Länge [mm]\ge 1[/mm]
Damit hast du schonmal Typ 1
Wenn die von der obigen Grammatik erzeugte Sprache von Typ >1 ist, so ist sie doch auch vom Typ 1!
Höhere Typen bedeuten doch nur weitere Einschränkungen.
> und
> Jetzt kann ich mich zwischen 2 und 3 nicht entscheiden bei
> Typ 2 steht hier ja eine Variable links alleine??
Bei Typ 3 doch auch.
Eine Grammatik vom Typ 2, wenn (zusätzlich zu der Typ 1-Eigenschaft) auf der linken Seite
der Produktionsregeln nur Nichtterminale auftreten, also Elemente aus NT
Das ist hier doch der Fall, da steht linkerhand doch nur [mm]S,A,B\in NT[/mm]
Damit hast du schonmal, dass die Grammatik vom Typ 2 ist.
Wie sieht es mit Typ 3 aus?
Das ist Typ 2 mit noch einer einschränkenden Eigenschaft für die rechte Seite der Produktionen. Welche und ist diese Eigenschaft hier erfüllt?
>
> oder Typ 3, weil auf der rechten Seite sind entweder
> einzelne Terminalzeichen oder ein Terminalzeichen gefolgt
> von einer Variablen.
Jo, das meine ich mit meiner Frage.
Gilt das hier?
Kannst du also Typ 2 noch zu Typ 3 einschränken?
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:12 Mo 05.12.2011 | | Autor: | emulb |
Da es einfache Zeichen waren, hab ich einfach die pdf kopiert aber anscheinend wird es bei anderen nicht so angezeigt wie bei mir. Sorry. ich merks mir :)
Typ 3 gilt somit auch, weil in S, A, und B sind Terminzeichen enthalten.
Also ist diese Grammatik ja Typ 0, weil 1,2,3 gelten :)
hab ich das jetzt richtig verstanden?
|
|
|
| |
|
Hallo nochmal,
> Da es einfache Zeichen waren, hab ich einfach die pdf
> kopiert aber anscheinend wird es bei anderen nicht so
> angezeigt wie bei mir. Sorry. ich merks mir :)
>
> Typ 3 gilt somit auch, weil in S, A, und B sind
> Terminzeichen enthalten.
Es geht doch um die rechten Seiten bei Typ 3
Stehen da überall nur einzelne Terminale oder ein Terminal gefolgt von einem Nichtterminal?
>
> Also ist diese Grammatik ja Typ 0, weil 1,2,3 gelten :)
Jo, jede Grammatik (in der C-Hierarchie) ist automat. vom Typ 0
>
> hab ich das jetzt richtig verstanden?
Da bin ich nicht ganz sicher ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:23 Mo 05.12.2011 | | Autor: | emulb |
Die rechte Seite beinhaltet ja Terminalzeichen:
Bei S ist es +
bei A ist es *
und B ist ja S also somit +.
|
|
|
| |
|
Hallo nochmal,
es darf auf der rechten Seite (einer jeden Regel) entweder nur genau ein einzelnes Terminalzeichen oder aber ein einziges Terminalzeichen gefolgt von einem einzigen Nichtterminalzeichen stehen.
Direkt bei der 2.ten Regel, also [mm] $S\to [/mm] S+A$ steht doch rechterhand $Nichtterminal (S) gefolgt von Terminal (+) gefolgt von Nichtterminal (A).
Das darf bei Typ 3 nicht sein!
Also liegt hier eine Typ 2-Grammatik vor.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:45 Mo 05.12.2011 | | Autor: | emulb |
aso ok jetzt sitzt es, danke :)
|
|
|
|
