reguläre Sprachen |
| 22.06.2004, 20:40 | franky.b | Auf diesen Beitrag antworten » | ||||||
| reguläre Sprachen das ist eine Frage für diejenigen, die, wie ich, das Vergnügen haben, in den Genuss der theoretischen Informatik zu kommen 
Vielleicht findet sich ja jemand, der das drauf hat...Also: gegeben sei die Sprache , wobei x^R das gespiegelte Wort x ist. Es handelt sich also um Palindrome gerader Länge mit einem Anhängsel y. So, nun soll ich zeigen, dass diese Sprache nicht regulär ist. Meine Überlegung ist nun, dass es sich bei dieser Sprache ja aus der Vereinigung der Sprachen und handelt. Ich würde also so vorgehen, dass ich sage:OK, L_2 ist sicher regulär, ich zeige also, dass L_1 nicht regulär ist (das ist nicht allzuschwer, mit dem Satz von Myhill&Nerode). Somit behaupte ich also dann: wenn L_1 nicht regulär ist, dann ist auch L nicht regulär, d.h. die Vereinigung aus einer nicht-regulären Sprache und einer regulären Sprache ist nie regulär. Stimmt das ? |
||||||||
| 22.06.2004, 21:17 | Mazze | Auf diesen Beitrag antworten » | ||||||
versuch es mit dem pumping-lemma argument Sei L eine reguläre Sprache dann gibt es eine Zahl n so das ich sich alle Wörter x aus L mit |x| <= n zerlegen lassen in x = uvw und das folgende eigenschaften gelten 1. |v| >= 1 2. |uv| <= n 3.für alle i = 0,1,2... gilt: So deine sprache ist also ich zerlege wie folgt u= x w= lambda nach definition 3 gilt muss in L sein => muss in L sein uv²w <=> Widerspruch, L kann nicht regulär sein, hoffe hab kein fehler gemacht
Da beide Mengeneigenschaften in eine Menge zusammengepackt werden kann die Vereinigung nicht regulär sein. |
||||||||
| 22.06.2004, 21:26 | franky.b | Auf diesen Beitrag antworten » | ||||||
hey, danke für die rasche antwort! :] man könnte das wohl auch mit dem pumping-lemma beweisen, aber in der aufgabe steht man muss es mit Myhill und Nerode machen 
Zudem ist dein Beweis nicht ganz richtig/vollständig, da du ja eine bestimmte Zerlegung gewählt hast, man aber eigentlich zeigen muss, dass es für ALLE möglichen Zerlegungen ein i gibt, so dass uv^iw nicht in L ist (meine ich zumindest 
Ich wollte ja eigentlich eh nur wissen, ob die Vereinigung aus einer regulären und einer nicht-regulären Sprache zwingend eine nicht-reguläre sein muss 
|
||||||||
| 22.06.2004, 21:28 | Mazze | Auf diesen Beitrag antworten » | ||||||
Wenn du beweisen willst das etwas nicht ist, dann nimm ein Gegenbeispiel und es ist nicht. Es reicht also eine zerlegung zu finden die nicht in L ist. das wurde getan. Myhill und Nerode kenn ich garnich -.-, kannst ma kurz erläutern? Hm habs mir grad bissel angelesen. es heißt also wenn die menge der Äquivalenzklassen bezüglich eines DFA M endlich ist, ist die sprache regulär. Du musst also zeigen, des es unendlich viele nicht äquivalente Worte in L gibt. Du ahst also ein Wort z du musst zeigen das xz yz und das die Äquivalenzklassen bezüglich nicht endlich sind |
||||||||
| 22.06.2004, 21:53 | franky.b | Auf diesen Beitrag antworten » | ||||||
ja schon, aber du musst schon die genaue Definition benutzen: das Pumping Lemma sagt: Also wenn die Sprache regulär ist, dann gibt es ein n, so dass es für alle Wörter z aus L mit Länge größergleich n eine Zerlegung gibt, die die Bedingungen des PL erfüllt. Nun musst du die genaue Negation dieser Aussage bilden, also: für alle n gibt es ein Wort mit Länge >= n, so dass für ALLE Zerlegungen uvw gilt: z=uvw und nicht (1), (2), (3). Bilde am besten direkt aus den Quantoren die Negation, dann sieht man es deutlicher. Naja ist ja jetzt auch egal... Der Satz von Myhill und Nerode besagt, dass eine Sprache genau dann regulär ist, wenn es endlich viele Äquivalenzklassen gibt, in die sich die Sprache unterteilen lassen kann. Die betrachtete Äquivalenzrelaztion ist dabei: xRy <=> (xz in L <=> yz in L). <--- OK hat sich ja jetzt erledigt, da warst du selber schneller *g* Aber darum geht es mir ja eigentlich garnicht, sondern nur um meine alte Frage, ob die Vereinigung aus einer regulären und einer nicht-regulären Sprache zwingend eine nicht-reguläre sein muss... 
|
||||||||
| 22.06.2004, 22:00 | Mazze | Auf diesen Beitrag antworten » | ||||||
Überlegmal, wir haben eine Menge {x in R:x < 0} und die Menge {x in r: x > 0} Wenn wir jetzt beide vereinigen, sind dann alle zahlen < 0?? (Also sind alle Wörter über der Sprache regulär?) zu deiner negation Wenn ich mathematisch widerlegen will dann drehe ich die Aussage nicht um sondern ich sag einfach damit ist die Behautptung widerlegt, und das funktioniert überall so. wenn ich zeigen will das ein homomorphismus nicht existiert geh ich auch nicht den umständlichen weg, sondern zeige das 2 grundterme nicht erhalten werden. |
||||||||
| Anzeige | ||||||||
|
|
||||||||
| 22.06.2004, 22:10 | franky.b | Auf diesen Beitrag antworten » | ||||||
hmm, ne, wenn wir die beiden mengen vereinigen,dann sind die zahlen >0 oder <0 . aber was willst du damit aussagen?
völlig richtig, denn durch das angeben von -1 hast du gezeigt, dass gilt: , was nämlich das selbe ist wie |
||||||||
| 22.06.2004, 22:13 | Mazze | Auf diesen Beitrag antworten » | ||||||
Wir können die Sprache auch als Menge ihrer Wörter (i.A. unendliche Menge) auffassen. Sei A regulär und B nicht regulär => die wörter über A sind regulär und die wörter über B sind nciht regulär jetzt vereinigen wir die Wörter, also die Sprache existieren dann nur reguläre Wörter in (diesen punkt bitte mit vorsicht genießen, weil ich nicht sicher bin ob es reicht eine sprache durch die menge ihrer Wörter zu definieren) zu dienem zweiten Punkt Ja sicher, aber ich mach mir nicht die mühe extra die negierte Aussage zu basteln sondern ich gebs einfach an und gut is. Weil ein Gegenbeispiel ist der allerbeste Gegenbeweis den es gibt. |
||||||||
| 22.06.2004, 22:22 | franky.b | Auf diesen Beitrag antworten » | ||||||
genau! das ist die frage, die ich mir stelle. also ein gegenbeispiel ist mir noch keins eingefallen, aber eine begründung eben auch nicht
ja, aber dasmit dem gegenbeispiel funktioniert dann, wenn du durch das "rumdrehen" einen Existiert-Quantor erzeugt hast(dann kannst du nämlich durch Angabe eines Wertes zeigen, dass wirklich einer existiert!) - aber im Falle des PL steht ja an der entsprechenden Stelle schon ein Existenz-Quantor, der dann in einen "ForAll"-Quantor gedreht wird. und bei "für alle" muss man wirklich "für alle" zeigen, da reicht ein einzelnes Beispiel, sprich eine einezlne, bestimmte Zerlegung, nicht. aber echt interessante diskussion hier :] |
||||||||
| 22.06.2004, 22:25 | Mazze | Auf diesen Beitrag antworten » | ||||||
doch sie reicht, da wir rausbekommen, das es ein Wort in der Sprache gibt das die Bedingung NICHT erfüllt. Eine Sprache ist genau dann regulär wenn ALLE worte regulär sind. Ist ein Wort erzeugbar durch die Grammatik das nicht regulär ist, sind nicht alle Wörter regulär, und damit die sprache nicht regulär. Dieses eine wort haben wir gefunden, ergo ist alles bewiesen was bewiesen werden musste. Sturer formalismus ist nicht immer das beste Mittel um eine Aussage zu widerlegen. Wobei ich weiß das es in der Theoretischen Informatik geraden um diesen sturen formalismus geht 
hier wirst du die antwort auf deine frage finden Und ja die vereinigung einer nicht regulären mit einer regulären ist nicht regulär und hier stehts |
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
