You are not logged in.

boy1818

Zuhörer

  • "boy1818" started this thread

Posts: 1

Date of registration: Jan 12th 2011

1

Wednesday, January 12th 2011, 12:54pm

Grundlagen der Informatik

Hallo erstmal.

Ich habe folgende Aufgabe, aber bin eig völlig hilflos und habe keinen Plan, was genau hier von mir gewollt wird.

Hier nun die Aufgabe:

a) Welche Sprache erzeugt die folgende Grammatik?

G=(N,T,P,w) mit N={R}, T={'x','y','z'}, P={R::= 'x''y' | 'x'R'y' |'z'}, w=R

Geben Sie die übliche Mengenaufzählung der Worte L(G)={….} an!

b) Welchen CHOMSKY-Typ hat diese Grammatik? Geben Sie die größte, mögliche
Typnummer an!
□ Typ 0 □ Typ 1 □ Typ 2 □ Typ 3

c) Ist diese Grammatik eindeutig? □ Ja □ Nein

Kann mir bitte jemand helfen?

hyperion

Erfahrener Schreiberling

  • "hyperion" is male

Posts: 422

Date of registration: Oct 8th 2004

2

Wednesday, January 12th 2011, 2:08pm

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.
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach

pythong

Trainee

  • "pythong" is male

Posts: 112

Date of registration: Oct 23rd 2005

Location: Ehemals Preußisches Gebiet

Occupation: Ehemals Studentenquäler. I'm finally done with school!

3

Wednesday, January 12th 2011, 10:45pm

@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?
don't ask me, google it