[Theoretische Informatik] Sprachklasse der Rationalen Zahlen

[F_GXdx]

Hallo Leute,

mir ist heute früh beim Rasieren was eingefallen, und ich konnte es heute bisher nicht lösen. Und zwar geht es um Automatentheorie: Was ist eigentlich der "schwächste" Automat, der die Rationalen Zahlen erkennen kann? Dabei soll Vorraussetzung sein, dass alle Eingaben, an den Automaten natürlich potentiell unendlich lang sein können, also die Zahl 2 wird zum Beispiel als 2,0000... eingegeben.

Was mich dabei stutzig macht ist die Beobachtung, dass man offensichtlich die Natürlichen Zahlen schon mit einem DFA bzw. regulären Ausdruck erkennen kann: [1-9][0-9]*,(0)*.

Offensichtlich existiert ja eine bijjektive Abbildung von den Natürlichen Zahlen in die Rationalen Zahlen. Für die Rationalen Zahlen scheinen aber NFAs nicht zu funktionieren.

Ich meine relativ einfach eine Grammatik aus den CFG's gefunden zu haben, die Q erkennt, das heißt, dass es also mit einem Kellerautomaten funktionieren würde. Sicher bin ich mir aber nicht, und außerdem wundert es mich, dass man für zwei gleich große Mengen zwei unterschiedliche Sprachtypen vorliegen hat.

Hat jemand von euch ne Idee? Google hat mir nicht wirklich geholfen und Wikipedia liefert teilweise Widersprüche.

Edit: Dazusagen möchte ich, dass die rationalen Zahlen nicht als "1/3" eingegeben werden sollen, sondern als 0,3*.

 

[NullPointer]

Das Problem ist einfach, daß die rationalen Zahlen, wenn du sie als Dezimalzahlen schreibst, sich syntaktisch nicht von den reellen Zahlen unterscheiden, d. h. um sie zu erkennen, müßte dein Automat nachrechnen - dafür sind die aber nicht wirklich geeignet Wenn du die Bruchschreibweise nimmst, dann geht's ganz einfach mit einem NFA.

 

[chloe]

Aber ist nicht jede Zahl, die man bspw. in '[0-9]+,?[0-9]*' eingeben kann, sowieso in Q?

 

[NullPointer]

Alle abbrechenden, ja - aber nicht, wenn du unendlich viele Nachkommastellen erlaubst

 

[F_GXdx]

Aber ist nicht jede Zahl, die man bspw. in '[0-9]+,?[0-9]*' eingeben kann, sowieso in Q?

Hmm die Irrationalen nicht, zum Beispiel auch Pi oder Wurzel(2). Das Problem ist ja, dass es unendliche lange Zahlen gibt, die in Q sind, und manche eben nicht.

 

[Graf-Porno]

Ich glaube du wirst um die Definition als Bruch nicht umher kommen, einfach weil Q so definiert ist. Da wie du schon festgestellt hast du mit den vorgestellten Lösungen auch andere Zahlenräume zulässt. Guck dir mal die formalen Definitionen an.

 

[F_GXdx]

Q ist aber auch definierbar als die Zahlen, deren Nachkommastellen irgendwann periodisch werden. Und so möchte ich sie auch eingeben.

 

[ice-breaker]

Das ist aber nur eine kleine Menge, und in der theoretischen Informatik musst du aber alles formal absolut korrekt abbilden, du darfst also nicht nur einen kleinen Teil abbilden, sondern musst den ganzen Wertebereich abbilden, und der umfasst eben weit mehr Zahlen als jene, die periodisch sind.

 

[Wahnfried82]

Hallo,


ich glaube, das Problem liegt schon in der Formulierung im Eingangspost begraben, denn du gehst davon aus, dass die Eingabewörter unendliche Länge besitzen. Wörter im Sinne der theoretischen Informatik sind aber immer "nur" endlich lang. Hierzu kommt auch, dass die Kleene'sche Hülle (also der *-Operator) im Falle z.B. a* eben nicht bedeutet, dass der Buchstabe a unendlich oft vorkommt, sondern beliebig, aber endlich oft.

Chloe hat also völlig recht mit der Aussage, dass der Ausdruck [0-9]+(,[0-9]+)? nur rationale Zahlen beschreibt, da diese Zahlen ja nur endlich viele Nachkommastellen haben.

Mit anderen Worten, Deine Eingabe einer periodischen rationalen Zahl wie z.B. 1/3 in Dezimalschreibweise kann überhaupt gar keine gültige Eingabe für einen NFA sein, da diese immer endlich lang sein müssen.

So habe ich das damals jedenfalls verstanden, ist aber schon ein paar Jahre her

 

[dcobra]

Sehe ich auch so, das liegt doch schon in der Definition eines endlichen Automaten. Wie willst du jemals den Endzustand erreichen bei 1/3? Solange sich der Automat "bewegt" hast du noch kein gültiges Wort, da kann die Zahl hinter dem Komma periodisch werden wie sie möchte.

 

[chloe]

Vielleicht sowas ...?

[0-9]+(\.([0-9]*p[0-9])?)?[0-9]*

Das ließe dann Sachen zu wie 0.p3

 

[dcobra]

Also wenn der TS das so gemeint hat Chloe, dann sind wir alle übers Ziel hinausgeschossen

Falls er es so gemeint hat wie ich denke, dann kann man wahrscheinlich mit gar keinem Automaten rationale Zahlen erkennen. Mit einem Kellerautomaten nicht und vielleicht auch mit einer Turingmaschine nicht (wobei ich nur die "klassische" kenne).

 

[F_GXdx]

Das ist aber nur eine kleine Menge, und in der theoretischen Informatik musst du aber alles formal absolut korrekt abbilden, du darfst also nicht nur einen kleinen Teil abbilden, sondern musst den ganzen Wertebereich abbilden, und der umfasst eben weit mehr Zahlen als jene, die periodisch sind.

Nein. Q sind genau alle Zahlen, die periodisch werden, das stimmt schon. Das Weglassen der 0* am Ende ist nur eine Schreiberleichterung, aber es ist trotzdem eine Periode.

Hallo,

ich glaube, das Problem liegt schon in der Formulierung im Eingangspost begraben, denn du gehst davon aus, dass die Eingabewörter unendliche Länge besitzen. Wörter im Sinne der theoretischen Informatik sind aber immer "nur" endlich lang. Hierzu kommt auch, dass die Kleene'sche Hülle (also der *-Operator) im Falle z.B. a* eben nicht bedeutet, dass der Buchstabe a unendlich oft vorkommt, sondern beliebig, aber endlich oft.

Ja, ich glaube, das liegt der Hund begraben. Ich habe ein bisschen recherchiert, und einige Sachen entdeckt: zB das Buch Authomatentheorie und Logik von Hofmann und den Wikipediaeintrag zu Omega-Automaten entdeckt. Leider bin ich noch nicht dazu gekommen, mich genauer damit zu beschäftigen, es stimmt aber: Unendliche Eingabewörter erfordern wohl eine (geringfügige) Modifizierung der klassischen Automaten.

Danke daher für die Tipps, ich glaube ich krieg das schon noch hin *g*, möchte nur noch eine Grammatik und einen Automaten aufstellen, dann bin ich zufrieden...