View Full Version : Beispiel 5.1
schrankk
09-11-2008, 14:01
Meine Lösung:
a) G1 regulär und kontextfrei; L(G1) reg, k.f. und monoton
b) G2 kontextfrei und monoton; L(G2) k.f. und monoton
c) G3 kontextfrei; L(G3) k.f. und monoton
habt ihr genauso? :o
vlg
KatzeImSack
09-11-2008, 16:45
Zerwus!
warum ist G2 bei Dir nicht monton?
Rest hab ich sonst auch so wie du...
Grüße!
Ich habe G2 auch als k.f und monton ... kann ma kurz wer erklären warum G1 nicht monton sind? Sind nicht alle Produktionen |alpha| <= |beta| ???
schrankk
09-11-2008, 17:01
Zerwus!
warum ist G2 bei Dir nicht monton?
Rest hab ich sonst auch so wie du...
Grüße!
A->Eps und B->Eps verletzten die Bedingung für monotone Grammatiken, nämlich die Länge des Leerwortes ist doch 0, und somit ist rechte Seite kleiner (kürzer) als Linke
schrankk
09-11-2008, 17:03
kann ma kurz wer erklären warum G1 nicht monton sind? Sind nicht alle Produktionen |alpha| <= |beta| ???
Es gibt die Produktion C-> Eps, und |C| => |Eps|, und somit ist die Bedingung für monotone Grammatiken nicht erfüllt!
A->Eps und B->Eps verletzten die Bedingung für monotone Grammatiken, nämlich die Länge des Leerwortes ist doch 0, und somit ist rechte Seite kleiner (kürzer) als Linke
In G2 gibts kein A->Eps und B-> Eps oO
schrankk
09-11-2008, 17:26
In G2 gibts kein A->Eps und B-> Eps oO
Ja, hast natürlich Recht!! Dann ist wohl G2 noch monoton dazu!
Bianconeri
09-11-2008, 18:53
Zu G1: Wie kann die Sprache monoton sein, wenn es die Grammatik nicht ist? Im Skriptum steht: Eine formale Sprache L heißt monoton, wenn Sie von einer monotonen Grammatik erzeugt wird. Regulär habe ich auch und damit ist sie natürlich auch kontextfrei.
Edit: Ich bin ein Idiot man kann ja ne andere Grammatik dafür verwenden.
Eine Sprache ist wenn sie regulär ist automatisch kontextfrei und monoton oder?
schrankk
09-11-2008, 19:05
Um festzustellen, was für eine Sprache gegeben ist, kommt noch Chomsky-Hierarchy ins Spiel (dieses hübsches farbiges Bildchen, wenn du VOs besuchst)... Also man bestimmt zuerst die kleinste Menge, zu der gegebene Sprache gehört, und dann ordnet diese Sprache zu allen Obermengen noch zu!! :thumb:
vlg
Bianconeri
09-11-2008, 21:12
Um festzustellen, was für eine Sprache gegeben ist, kommt noch Chomsky-Hierarchy ins Spiel (dieses hübsches farbiges Bildchen, wenn du VOs besuchst)... Also man bestimmt zuerst die kleinste Menge, zu der gegebene Sprache gehört, und dann ordnet diese Sprache zu allen Obermengen noch zu!! :thumb:
vlg
OK danke kann mich schon erinnern an die Grafik war mir nicht sicher.
Aber noch 2 andere Fragen?
b) Die erzeugt Sprache ist {a^n b^(n+1) | n >= 0} oder?
c) ist die erzeugte Sprache da nicht {00}* ? Und das wäre doch regulär oder, kann man ja sogar nen Automaten dafür zeichnen.
Ultrazauberer
10-11-2008, 05:08
Meine Lösung:
a) G1 regulär und kontextfrei; L(G1) reg, k.f. und monoton
b) G2 kontextfrei und monoton; L(G2) k.f. und monoton
c) G3 kontextfrei; L(G3) k.f. und monoton
habt ihr genauso? :o
vlg
Sitz jetzt schon wieder ewigkeiten (3. Tag, jeweils bis mindestens um die jetztige Urzeit. Reallife und Private Life kommt ein anderes mal wieder) dabei, muss noch immer den Stoff der letzten Runden aufholen und hat deshalb wohl nich ganz so viel Sinn das hier anzugehen (Dennoch: Hoffnung stirbt zuletzt :) )
Kannst mir in Stichworten sagen, wie du da vorgegangen bist, bzw wonach ich mich im Skriptum orientieren sollte? Wär total nett. Danke!
Nur die Form der Produktionen ansehen... im Skriptum steht ziemlich genau wie eine
reguläre/kontextfreie und/oder montone Grammatik auszusehen hat.
Danach kann man von der Grammatik auf die Sprache schließen und da kommt die Chomsky-Hierachie ins Spiel... L(reg) echte teilmenge L(k.f.) echte teilmenge L(monton).
Zu G1: Wie kann die Sprache monoton sein, wenn es die Grammatik nicht ist? Im Skriptum steht: Eine formale Sprache L heißt monoton, wenn Sie von einer monotonen Grammatik erzeugt wird. Regulär habe ich auch und damit ist sie natürlich auch kontextfrei.
Edit: Ich bin ein Idiot man kann ja ne andere Grammatik dafür verwenden.
Eine Sprache ist wenn sie regulär ist automatisch kontextfrei und monoton oder?
Welche Grammatik findest du denn für {0}*{11}{0}* die monoton ist? Das ist ja die spräche die bei a) erzeugt wird
Laß ich die Produktion C->eps Weg hab ich hinten {0}+ meiner Meinung nach.
Nach dem ich die Postings hier gelesen habe, bin ich mir nicht mehr sicher ob meine Lösung stimmt :confused:
Erstens wie kann man daraufkommen, dass eine nicht monotone Grammatik wie G1 eine monotone Sprache generiert??? Da habe ich wegen dem Satz im Skriptum angenommen, dass da auch die Sprache L(G1) nicht monoton ist.
Wobei ich Chomsky hierarchie nicht so richtig kapiert habe.
Obwohl da gar nicht mal diskutiert wird, traue ich mich zu Fragen :)
und zwar : Warum ist L(G3) monoton,
Laut Definition --> Wenn Die Produktionen A->eps und B-> eps schon in der Grammatik vorkommen, dann dürfen sie nicht mehr auf der rechten Seite der Produktionen stehen, obwohl sie das schon tun.
Ich glaube G3 sollte auch nicht monoton sein und somit auch die Sprache nicht monoton.
Was denkt ihr, schreit bitte gleich wenn ich da ein blödsinn eingetippt habe
Bianconeri
10-11-2008, 23:39
Nach dem ich die Postings hier gelesen habe, bin ich mir nicht mehr sicher ob meine Lösung stimmt :confused:
Erstens wie kann man daraufkommen, dass eine nicht monotone Grammatik wie G1 eine monotone Sprache generiert??? Da habe ich wegen dem Satz im Skriptum angenommen, dass da auch die Sprache L(G1) nicht monoton ist.
Wobei ich Chomsky hierarchie nicht so richtig kapiert habe.
Obwohl da gar nicht mal diskutiert wird, traue ich mich zu Fragen :)
und zwar : Warum ist L(G3) monoton,
Laut Definition --> Wenn Die Produktionen A->eps und B-> eps schon in der Grammatik vorkommen, dann dürfen sie nicht mehr auf der rechten Seite der Produktionen stehen, obwohl sie das schon tun.
Ich glaube G3 sollte auch nicht monoton sein und somit auch die Sprache nicht monoton.
Was denkt ihr, schreit bitte gleich wenn ich da ein blödsinn eingetippt habe
Es hat ja auch keiner behauptet, dass die Grammatik G3 monton ist. Die Sprache hingegen ist meiner Meinung nach sogar regulär. Ist doch {00}*. Reguläre Sprache ist wie man an der Chomsky Hierarchie sieht auch kontextfrei und monoton.
ja aber wenn die Grammatik schon die Bedingungen der monotonie stört, kann man auch behaupten, dass die davon erzeugte Sprache auch "nicht monoton" ist.
Eine Sprache heisst monoton, wenn Sie von einer monotonen Grammatik erzeugt wird. (Skriptum)
Natürlich sagt ihr, dass diese Grammatik auch monotone Sprachen erzeugen kann, aber wie ist es zu begründen.
Sagt bitte nicht ---> Chomsky Hierarchie, das Zeug habe ich gelesen und kann nicht kappieren was damit gemeint ist....
Mir gehts ähnlich. Wie kann ne Sprache monoton sein, wenn es keine monotone Grammatik gibt, die sie erzeugt?
Außerdem ... Laut d er Chromsy-Hierarchie ist bei Typ-3 Grammatiken, also reguläre Grammtiken die Produktion A->b b aus T erlaubt ... Aber paar seiten vorher steht A->bA oder A->eps .. soviel ich weiß..
Markus1201
11-11-2008, 12:22
Ein Versuch die ganzen Missverständnisse zu diesem Thema zu klären:
Eine Sprache kann von vielen Grammatiken erzeugt werden.
Egal durch welche Grammatik die Sprache angegeben wird, ist sie möglicherweise trotzdem durch eine Grammatik darstellbar, die regulär, kontextfrei oder monoton ist.
Laut Chomsky Hierarchieist eine reguläre Sprache (nicht Grammatik) auch immer kontextfrei beziehungsweise monoton, eine kontextfreie ist auch immer monoton.
schrankk
11-11-2008, 18:28
ja aber wenn die Grammatik schon die Bedingungen der monotonie stört, kann man auch behaupten, dass die davon erzeugte Sprache auch "nicht monoton" ist.
Eine Sprache heisst monoton, wenn Sie von einer monotonen Grammatik erzeugt wird. (Skriptum)
Um behaupten zu dürfen, dass eine Sprache "nicht monoton" ist, solltest du ja alle Grammatiken dursuchen, die diese Sprache erzeugen können (vile Spaß damit! ;)). Um behaupten zu dürfen, dass eine Sprache "nicht k.f." oder "nicht regulär" ist, reichen P.L. oder Abschlusseigenschaften. Naja, mit Hilfe von Abschlußeigenschaften für monotone Sprachen könntest du auch versuchen zu widerlegen, dass eine Sprache "nicht monoton" ist.
Natürlich sagt ihr, dass diese Grammatik auch monotone Sprachen erzeugen kann, aber wie ist es zu begründen.
Sagt bitte nicht ---> Chomsky Hierarchie, das Zeug habe ich gelesen und kann nicht kappieren was damit gemeint ist....
Eine reg. (k.f.) Sprache ist automatisch auch monotone in allen Fällen! Genau das beschreibt C.H. Und Verweis auf C.H. ist genau ne Begründung, die du in diesem Bsp brauchst! :thumb:
schrankk
11-11-2008, 18:33
Mir gehts ähnlich. Wie kann ne Sprache monoton sein, wenn es keine monotone Grammatik gibt, die sie erzeugt?
Woher weißt du das? :rolleyes:
bei Typ-3 Grammatiken, also reguläre Grammtiken die Produktion A->b b aus T erlaubt ... Aber paar seiten vorher steht A->bA oder A->eps .. soviel ich weiß..
Schau dir die Folie Seite 61 :thumb:
Ich hab ne Frage zur C.H.
Da steht bei Regulärer Grammatik ist auch A->b erlaubt. Wikipedia sagt das auch.
Im Skriptum unter regulär steht aber A->bA und A->eps ...
Was ist jetzt? Ist A->eps erlaubt? Sollte ja weil {0}* wäre regulär und da brauch ich ja das leerwort? Und naja was ist nun richtig?
Ich hab ne Frage zur C.H.
Da steht bei Regulärer Grammatik ist auch A->b erlaubt. Wikipedia sagt das auch.
Im Skriptum unter regulär steht aber A->bA und A->eps ...
Was ist jetzt? Ist A->eps erlaubt? Sollte ja weil {0}* wäre regulär und da brauch ich ja das leerwort? Und naja was ist nun richtig?
Jede reguläre Grammatik ist auch kontextfrei (A -> b ). Siehe Skript
Mfg
Woher weißt du das? :rolleyes:
das weiß ich nicht, aber wie soll ich zB {0}* monoton darstellen? Monton heißt ja immer |alpha| <= |beta|. Aber wenn beta => eps ist, dann gilt das doch nicht oder? Und wie bekomme ich den * hin, also "nix" wenn eps nicht zulässig ist? Wenn du mir das beantwortest bin ich glücklich
Schau dir die Folie Seite 61 :thumb:
Ja "Alternativ". Heißt das jetzt Entweder Oder? ALso nen Exclusives Oder der Variante [1] und [2] oder kann ich die vermischen?
schrankk
11-11-2008, 18:48
Ja "Alternativ". Heißt das jetzt Entweder Oder? ALso nen Exclusives Oder der Variante [1] und [2] oder kann ich die vermischen?
Da denkst du schon zu tief!! ;)
Schau einfach, ob es die gegeben Grammatik laut Def[1] oder vl. laut Def.[2] regulär ist?! Falls die Produktionen beide Def verletzten, dann ist die gegebene Grammatik nicht regulär! Falls die Produktionen nur eine Def verletzten, ist die gegebene Grammatik doch regulär!
Da denkst du schon zu tief!! ;)
Schau einfach, ob es die gegeben Grammatik laut Def[1] oder vl. laut Def.[2] regulär ist?! Falls die Produktionen beide Def verletzten, dann ist die gegebene Grammatik nicht regulär! Falls die Produktionen nur eine Def verletzten, ist die gegebene Grammatik doch regulär!
wieso denk ich zu tief meine frage war nur ob jetzt eine grammatik die beides hat zB
A->aB und A->a auch regulär ist.
ODer dürfen nur A->a vorkommen ODER nur A->aB .. das war ne normale Frage ... ist doch nicht zu tief? :)
schrankk
11-11-2008, 18:56
wieso denk ich zu tief meine frage war nur ob jetzt eine grammatik die beides hat zB
A->aB und A->a auch regulär ist.
ODer dürfen nur A->a vorkommen ODER nur A->aB .. das war ne normale Frage ... ist doch nicht zu tief? :)
dann verstehe ich dir gar nicht!! Besser und verständlicher, als es in Folien steht, kann ich leider nicht ausdrücken!!
vlg
also bei mir ist G1 und G2 regulär, oder bincih da totalauf dem holzweg?
also bei mir ist G1 und G2 regulär, oder bincih da totalauf dem holzweg?
Siehe erster Post von schrankk ... Schau dir mal G2 an die Produktionen sind nicht regulär.
eine frage:
L(G3) monoton
d.h. es müsste eine monotone grammatik geben die G3 erzeugt.
jedoch kann ich mir keine monotone grammatik vorstellen, die mir epsilon erzeugt.
ah ok moment. geht folgendes?
A -> ABA|B|C, B -> 00
jperl
ok is klar wegen der chomsky hierarchie.
jede reguläre sprache ist kontextfrei und jede kontextfreie sprache auch monoton, wegen der teilmengenbeziehung.
achtung bei L(G3). diese ist auch regulär (hatte gerade tutorium).
jperl
matthiasb
12-11-2008, 19:05
Hätte folgendes für die Sprachen rausbekommen:
L(G_{1}) regulär (in Folge der Chomsky-Hierarchie auch kontextfrei und monoton) weil ich äquivalent \{\underline{0}\}*\{\underline{1}\underline{1}\}\{ \underline{0}\}* schreiben könnte.
L(G_{2}) ist kontextfrei (und monoton) da für die Sprache \{\underline{a}^{n}\underline{b}^{n+1}|n\geq 0\} gilt.
L(G_{3}) ist wieder regulär, da die Grammatik \{\underline{0}\underline{0}\}^{*} erzeugt.
Für die Grammatiken selbst weiß ich nicht wie die Einordnungen zu treffen sind. Sonst würd ich die Form der Produktionen alleine beurteilen, ob sie sich in eine Normalform bringen lassen. Tabelle Skriptum S.61 wie oben erwähnt.
(Also G1 regulär, G2 kontextfrei, G3 kontextfrei)
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.