Hi!

Kann mir jemand mal einen Tip zu dieser Aufgabe geben, komme da nicht weiter…

zu (i)
Reicht es aus, wenn ich so anfange, dass ich ein Wort suche, dass nicht mit dem rationalen Ausdruck von A und B beschrieben werden kann..

wenn ja, wie kann ich das machen?

Gruß

falls zu wenige antworten kann es daran liegen
dass alle ausser in deinem Jahrgang die Aufgabe nicht kennen

Reicht es aus, wenn ich so anfange, dass ich ein Wort suche, dass nicht mit dem rationalen Ausdruck von A und B beschrieben werden kann..

Das ist gerade die Aufgabe?!

wenn ja, wie kann ich das machen?

Das wäre die Lösung?! Sind doch deine Hausaufgaben [img]http://www.fb18.de/gfx/25.gif[/img]

Guck dir mal die Entscheidungsprobleme im Skript an. Bei z.B. 3.76/3.77 kann man ganz gut sehen, wie man bei solchen Fragestellungen vorgehen kann. (Was ist eigentlich gesucht? Wie kann ich das auch ausdrücken (bspw. durch den Schnitt von bestimmten Mengen etc.) und zuletzt: kann ich dazu Automaten konstruieren (oder auch mit regulären Ausdrücken arbeiten)?
(Falls ja ist in dieser Aufgabe ein Verweis auf die Stelle im Skript verlangt.))

Cheers.

Aber kann nicht die Frage 8.1 (i) sofort bejaht werden? Wir wissen doch das es nicht-reguläre Mengen gibt welche nicht durch einen rationalen Ausdruck beschrieben werden können. D.h. es muss doch ein Wort aus einer nicht-regulären Menge geben welches weder vom rationalen Ausdruck A noch von B beschrieben wird.

Insofern verstehe ich die Problemstellung nicht.

Aber kann nicht die Frage 8.1 (i) sofort bejaht werden? Wir wissen doch das es nicht-reguläre Mengen gibt welche nicht durch einen rationalen Ausdruck beschrieben werden können. D.h. es muss doch ein Wort aus einer nicht-regulären Menge geben welches weder vom rationalen Ausdruck A noch von B beschrieben wird.

Insofern verstehe ich die Problemstellung nicht.

Ich glaube es geht darum für beliebige Menge eine Weg zu finden wie man diese Fragen beantworten kann. D.h. ob deine Frage mit ja oder mit nein beantwortet wird hängt von den rationalen Ausdrücken A und B ab.

Hier wird natürlich (implizit) benötigt, dass die rationalen Ausdrücke (und die in der Fragestellung angesprochenen Wörter) über dem gleichen Alphabet definiert sind.

Ansonsten ist es natürlich immer möglich ein Wort zu finden, dass weder in M_A noch in M_B ist. (Ist A bspw. ein rationaler Ausdruck, der das d nicht enthält und B einer, der kein q enthält, dann mache ich mir einfach das Wort 'dq', aber das ist so wirklich nicht gemeint.)

Cheers.