reguläre Sprachen

Neue Frage »

franky.b Auf diesen Beitrag antworten »
reguläre Sprachen
Hallo Leute,

das ist eine Frage für diejenigen, die, wie ich, das Vergnügen haben, in den Genuss der theoretischen Informatik zu kommen smile 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 ?
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

Zitat:
h. die Vereinigung aus einer nicht-regulären Sprache und einer regulären Sprache ist nie regulär.


Da beide Mengeneigenschaften in eine Menge zusammengepackt werden kann die Vereinigung nicht regulär sein.
 
 
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 unglücklich
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 Augenzwinkern

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 verwirrt
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
franky.b Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
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.

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... Wink
Mazze Auf diesen Beitrag antworten »

Zitat:
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...


Ü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.
franky.b Auf diesen Beitrag antworten »

Zitat:
Original von Mazze

Ü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 < x??
(Also sind alle Wörter über der Sprache regulär?)



hmm, ne, wenn wir die beiden mengen vereinigen,dann sind die zahlen >0 oder <0 . aber was willst du damit aussagen?

Zitat:
Original von Mazze

zu deiner negation

Wenn ich mathematisch widerlegen will



dann drehe ich die Aussage nicht um



sondern ich sag einfach





völlig richtig, denn durch das angeben von -1 hast du gezeigt, dass gilt:
, was nämlich das selbe ist wie
Mazze Auf diesen Beitrag antworten »

Zitat:
hmm, ne, wenn wir die beiden mengen vereinigen,dann sind die zahlen >0 oder <0 . aber was willst du damit aussagen?


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.
franky.b Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
Zitat:
hmm, ne, wenn wir die beiden mengen vereinigen,dann sind die zahlen >0 oder <0 . aber was willst du damit aussagen?


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


genau! das ist die frage, die ich mir stelle. also ein gegenbeispiel ist mir noch keins eingefallen, aber eine begründung eben auch nicht unglücklich


Zitat:
Original von Mazze
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.

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 :]
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 Big Laugh

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
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »