Fachrat Informatik - Forum

Also zu a)

Du sollst angeben, welche Worte sich mit dieser Grammatik bilden lassen. Ich gehe mal davon aus, dass Dir klar ist, was N, T, P und w in diesem Fall sind, oder?

zu b) Für die Einteilung in die Chomsky Hierachie wurden in der Vorlesung doch verschiedene Kriterien genannt. Schau Dir mal die Produktionen der Grammatik an und entscheide dann, in welchen Typ diese Grammatik gehört.

zu c) Was bedeutet den Eindeutigkeit? Gibt es mit dieser Grammatik immer nur einen Weg ein Wort zu bilden oder hast Du vielleicht zwei oder mehr Wege, mit Hilfe der Produktionen ein Wort zu erzeugen?

Hoffe, ich konnte Dich schon mal in die richtige Richtung schubsen.

@hyperion: ich glaub, ihm ist nicht ganz klar, was die symbole heißen, denn die aufgabe ist eigtl super einfach...

ich versuch mal, das suuuuper-banal zu erklären. vorsicht: ist wirklich absichtlich auf 'stumpf' gehalten, und sobald Arne hier reinschaut, verhaut er mich wohl ;D

also:
N sind Nichtterminale. Stell dir Nichtterminale als 'Fabriken' vor, die 'Sachen' produzieren. Die 'Sachen' können Endprodukte oder andere Fabriken oder beides sein. Angenommen, ich habe N = {S,U}, dann habe ich eine 'Fabrik' S und eine 'Fabrik' U. Nichtterminale werden in der Regel mit Großbuchstaben angegeben

T sind Terminale. Stell dir das als Endprodukt vor (lat.: terminus). das ist das, was du haben willst. du willst am ende keine weiteren Fabriken sehen, sondern nur Endprodukte. Terminale werden idR mit Kleinbuchstaben angegeben

P sind Produktionen. Sie geben an, was die Fabriken produzieren. Wenn also gilt: P = {S ::= aS, S ::= Ub, U::= c}, dann habe ich die folgenden drei Regeln:
1) Eine Fabrik S stellt links von sich ein 'a' her (die alte Fabrik S bleibt rechts davon bestehen)
2) Eine Fabrik S kann zu einer Fabrik U werden, mit rechts daneben einem Endprodukt 'b'. (die alte Fabrik S verschwindet)
3) Eine Fabrik U stellt ein 'c' her (und verschwindet)

w gibt an, womit du anfängst. sei zB hier 'w = S', dann fängst du mit einer Fabrik S an.

Jetzt ist die Frage, was kannst du alles herstellen? Das ist L(G) und darf keine Fabriken mehr enthalten. Ist wie mit Legos spielen, nicht groß nachdenken, sondern machen.
Erstmal wild testen:
Beispiel 1: S -> aS -> aaS -> aaUb -> aacb. Jetzt hab ich nur noch Terminale und kann nix mehr herstellen
Beispiel 2: S -> aS -> aaS ->....-> aaaaaaaaaaaaaaaaaaaaaaaS-> aaaaaaaaaaaaaaaaaaaaaaaUb -> aaaaaaaaaaaaaaaaaaaaaaacb. Wieder hab ich nur noch Terminale und kann nix mehr herstellen

Also, L(G) = {aacb, aaaaaacb, acb, ...} huh? zu lang, macht keinen Spaß
Jetzt bist du ein Informatiker und machst das natürlich schlauer durch scharfes Hinschauen, was alles rauskommen kann.
L(G) sollte hier L(G)={a^n c b| n >= 1} sein, weil ich theoretisch unendlich viele 'a's und mindestens eins erstellen kann/muss. (Ich erinner mich grad nicht, ob man angeben muss, dass n element Natürliche Zahlen ist. Richte dich nach der Übung)

für die aufgabenteile b und c solltest du dir die definitionen anschauen. am leichtesten fand ich persönlich immer die definition über die automaten, aber das muss jeder für sich sehen. Übung macht den Meister, ne?