Fachrat Informatik - Forum

Hi,

hat jemand eine Idee, wie man diese Aufgabe löst:


[img]http://forum.finf.uni-hannover.de/[url='http://img8.imageshack.us/my.php?image=tasko.jpg'][img]http://img8.imageshack.us/img8/6806/tasko.th.jpg[/img][/url][/img]

Viele Grüße

Quoted from "hyperion"

Ich würde mal darauf tippen, dass Du Dir zuerst überlegst, welche Zahlen Du mit diesen Ausdrücken darstellen kannst.

Zum Beispiel für alpha1:

1(0|1)+000

Das sind ja schon mal mindestens 5 Zahlen. Die fünfte Ziffer in der Binärdarstellung steht ja für 16. Somit sind diese Zahlen ja alle grösser als 16. Es sind aber nicht alle Zahlen über 16 in dieser Menge, da die ersten drei Stellen ja 0 sind.

Hm...ich sehe hier nur 2 Zahlen des Dualsystems: 10000 und 11000 - die erste Zahl ist 16 im Dezimalsystem wie erwähnt und die zweite Dualzahl ist 1*2^4 + 1*2^3 = 24. Somit ist eigentlich auch nur eine Zahl größer als 16 (nämlich die 24) und die 16 ist lediglich echt größer als 16 (also gleich groß). Den letzten Satz hab ich nicht verstanden - denn aus meiner Sicht besteht die Dualzahl aus mindestens 5 Ziffern und somit ist sie stets mindestens so groß wie 16 im Dezimalsystem.

Quoted

Gesucht ist als Antwort entweder ein Satz der folgenden Art (diese Beispiel sind nicht aus der Aufgabe!):

Der Reguläre Ausdruck beschreibt Zahlen in Dualdarstellung, die größer als 32 und durch 4 teilbar sind.

Alternativ tut es auch eine Mathematische Mengedefinition wie etwa:
[img]http://forum.finf.uni-hannover.de/mimetex.cgi?%5C%7Bx%7Cx%3E32%2Cx%20%3D%200%20mod%204%5C%7D[/img]

wie kommst du auf die Definition des regulären Ausdrucks? -nicht jede Dualzahl in dem von hyperion ausgesuchten Beispiel ist größer als 32...z.B. 10000 und ich glaub nicht, dass jede Zahl in Dualdarstellung durch 4 teilbar sein muss, um ein regulärer Ausdruck zu sein.
Reguläre Ausdrücke gehen lt. Skript der Veranstaltung, S. 31,32 und 29, eher auf reguläre Sprachen zurück und sollen diese beschreiben. Diese reguläre erzeugte Sprache wird von einer regulären Grammatik erzeugt.

Definition: Eine kontextfreie Grammatik G=(N,T,P,S) heisst regulär, wenn alle Produktionen in P die Form A -> alpha*B oder A -> alpha mit A,B e N, alpha e T* haben.

"Reguläre Ausdrücke werden...rekursiv definiert." "Ein regulärer Ausdruck alpha über ein Alphabet T bezeichnet immer eine Menge von Wörtern L(alpha) C T*, also eine formale Sprache über T."

Bei der Zusammensetzung eines regulären Ausdrucks ist ferner zu beachten: "Um die Zahl der Klammern gering zu halten, vereinbart man üblicherweise eine Prioriätsordnung, und zwar haben * und + die höchste Priorität, dann kommt das Produkt und schließlich die Vereinigung. Alle Operationen sind linksassoziativ."

Beispiel einiger Operationen: M^0 = {epsilon} ; M^1 = M; M^i = M*M^(i-1) ; M* = Summe aller Vereinigungen über M^i von 0 bis unendlich; M+ = Summe aller Vereinigungen über M^i von 1 bis unendlich (also ohne 0)

Konkretes Beispiel: alpha = a | bc*d = a((b(c)*)d) und bezeichnet die formale Sprache L(alpha)={alpha} Vereinigung {bc^(i)d | i>=0}

Quoted from "oixio"

]

bedeutet das beliebig viele 0en und 1en folgen dürfen, aber die Zahl mindestens aus einer 0 oder 1 besteht.

...ja, wenn man im ersten Beispiel 1(0|1)+000 den Ausdruck (0|1)+ als Menge M+ auffasst, ergibt sich anscheinend eine unendliche Lösung...ob eine Beschreibung der Mengen in Dualdarstellung ausreichend ist?

-Zum Beispiel sämtliche Binärzahlen "beginnen" mit einer 1 und "enden" stets mit 3 Nullen.

Für M={1,0} folgt dann M²={00,01,10,11}, M^3={000,001,010,011,100,101,110,111} => M+={1,0}v{00,01,10,11}v{000,001,010,011,100,101,110,111}v...

Eingesetzt in die erste Aufgabe: 1({1,0}v{00,01,10,11}v{000,001,010,011,100,101,110,111}v...)000

Quoted

Ich würde also erstmal zusehen, dass du dir genau anschaust, was für Binärzahlen der reguläre Ausdruck erzeugt.

Dann müssten das folgende Binärzahlen sein: 10000, 11000, 100000, 101000, 110000, 111000, 1000000, 1001000, 1010000, 1011000, 1100000, 1101000, 1110000, 1111000,...

Quoted

Im Skript müsste genau definiert sein, wie ein Regulärer Ausdruck ausgewertet wird.

Ja, siehe mein Vermerk oben.

Quoted

Und wenn das klar ist, dann schau dir an, was das in Dezimal-Zahlen umgerechnet ist.

könnte man machen, ist aber laut Aufgabenstellung nicht gefordert...zur Ergänzung rechne ich die Binärzahlen trotzdem mal um, vielleicht sieht man ja was lustiges:

10000, 11000, 100000, 101000, 110000, 111000, 1000000, 1001000, 1010000, 1011000, 1100000, 1101000, 1110000, 1111000

16 , 24 , 32 , 40 , 48 , 56 , 64 , 72 , 80 , 88 , 96 , 104 , 112 , 120 ...alles Vielfache von 8!