Sie sind nicht angemeldet.

BJETIT

Praktikant

  • »BJETIT« ist der Autor dieses Themas

Beiträge: 14

Registrierungsdatum: 16.01.2009

1

25.04.2009, 20:11

Programmiersprachen und Übersetzer / Aufgabe zum Thema "Reguläre Ausdrücke"

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

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »BJETIT« (25.04.2009, 20:12)


hyperion

Erfahrener Schreiberling

  • »hyperion« ist männlich

Beiträge: 422

Registrierungsdatum: 08.10.2004

2

25.04.2009, 20:24

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.
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach

oixio

Senior Schreiberling

  • »oixio« ist männlich

Beiträge: 517

Registrierungsdatum: 03.10.2004

3

25.04.2009, 20:47

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:
Dieser Post wurde aus 100 % chlorfrei gebleichten, handelsüblichen, freilaufenden, glücklichen Elektronen erzeugt!

Rick

Mädchen

  • »Rick« ist männlich

Beiträge: 1 266

Registrierungsdatum: 17.03.2004

Wohnort: ::1/128

Beruf: Forentroll

4

25.04.2009, 21:02

Ich korrigiere das mal schnell:

Sometimes you've got to ask yourself: Is xkcd shitty today?

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Rick« (25.04.2009, 22:37)


BJETIT

Praktikant

  • »BJETIT« ist der Autor dieses Themas

Beiträge: 14

Registrierungsdatum: 16.01.2009

5

25.04.2009, 21:44

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.



Zitat

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}

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »BJETIT« (25.04.2009, 22:05)


oixio

Senior Schreiberling

  • »oixio« ist männlich

Beiträge: 517

Registrierungsdatum: 03.10.2004

6

25.04.2009, 22:11

wie kommst du auf die Definition des regulären Ausdrucks?

Zunächst einmal, ich habe nur beispielhafte Antworten gegeben, die nichts mit den konkreten Regulären Ausdrücken in den Aufgaben zu tun hatten.

Hm...ich sehe hier nur 2 Zahlen des Dualsystems: 10000 und 11000


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

Ich würde also erstmal zusehen, dass du dir genau anschaust, was für Binärzahlen der reguläre Ausdruck erzeugt. Im Skript müsste genau definiert sein, wie ein Regulärer Ausdruck ausgewertet wird.

Und wenn das klar ist, dann schau dir an, was das in Dezimal-Zahlen umgerechnet ist.
Dieser Post wurde aus 100 % chlorfrei gebleichten, handelsüblichen, freilaufenden, glücklichen Elektronen erzeugt!

BJETIT

Praktikant

  • »BJETIT« ist der Autor dieses Themas

Beiträge: 14

Registrierungsdatum: 16.01.2009

7

25.04.2009, 22:36

]

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

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




Zitat

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,...




Zitat

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

Ja, siehe mein Vermerk oben.




Zitat

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!

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »BJETIT« (25.04.2009, 22:49)


Markus

the one and only Unterstrich!

Beiträge: 2 571

Registrierungsdatum: 09.10.2003

8

26.04.2009, 11:19

alles Vielfache von 8!
Meint ihr, der Groschen ist gefallen? :D
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...