Grammatik: Durch 6 teilbare Zahl konstruieren?



  • Hi Leute!

    Ich soll eine Grammatik erstellen (Typ ist keiner vorgegeben!) der eine durch 6 teilbare Zahl erstellen lässt. Ich hab mir nun natürlich schon Gedanken zu solchen Zahlen gemacht und dabei auf folgendes gestoßen:

    Eine durch 6 teilbare natürliche Zahl hat an niederwertigster Stelle immer eine 0,2,4,6 oder 8 UND ihre Quersumme ist ohne Rest durch 3 teilbar.

    Des Weiteren hab ich nun auch schon mal Regeln aufgestellt, die mir sicherstellen, dass an der niederwertigsten Stelle nur gerade Zahlen stehen:

    G={V,,P,S}G=\{V, \sum, P, S\}, V={S,A,B,C,D,E}V=\{S, A, B, C, D, E\}, ={0,...,9}\sum = \{0, ..., 9\}, P={S0,SAB,SE,Aϵ,ACD,CCD,B0,B2,B4,B6,B8,E6}P=\{S\to 0, S \to AB, S \to E, A \to \epsilon, A \to CD, C \to CD, B \to 0, B \to 2, B \to 4, B \to 6, B \to 8, E \to 6\}

    Jetzt hab ich nur noch das Problem, wie ich die die Zahlenmenge für C und D so einschränke, dass auch wirklich die Quersumme 3 wird... Jedenfalls darf man für C bei den Regeln erst bei 1 beginnen, da führende Nullen nicht erlaub sind

    Kann mir jemand helfen?



  • Wie muss ich anfangen? Ist es besser erst eine Grammatik zu entwerfen, die Zahlen erstellt, bei denen die Quersumme 3 ergibt, oder eine Grammatik die gerade Zahlen konstruiert.

    Ich hab mittlerweile beide Grammatiken entworfen. Ich muss die jetzt nur noch irgendwie zusammenführen. Kann mir jemand helfen, oder ist das ein schier unlösbares Problem?



  • Der Rest einer Summe A+B bei Division durch N ist (Div_N_Rest(A) + Div_N_Rest(B)) mod N .
    Das Anhängen einer Ziffer an eine bestehende Ziffernfolge kannst du als Addition darstellen, nämlich 10 * Zahl(Ziffernfolge) + NeueZiffer .

    Also A = 10 * Zahl(Ziffernfolge) und B = NeueZiffer .
    Netterweise bleibt der Rest bei Division durch 3 bei multiplikation mit 10 gleich.
    D.h. wenn wir eine Ziffernfolge X und eine Ziffernfolge Y haben dann gilt Div_3_Rest(10 * X + Y) = (Div_3_Rest(X) + Div_3_Rest(Y)) mod 3 .

    Das können wir jetzt verwenden um Regeln für Ziffernketten zu bilden, die bei Division durch 3 jeweils einen bestimmten Rest haben.

    Also...

    Div_3_Rest_0_Ziffer := 0 | 3 | 6 | 9
    Div_3_Rest_1_Ziffer := 1 | 4 | 7
    Div_3_Rest_2_Ziffer := 2 | 5 | 8
    
    Div_3_Rest_0_Zahl := Div_3_Rest_0_Ziffer | Div_3_Rest_0_Zahl Div_3_Rest_0_Ziffer | Div_3_Rest_1_Zahl Div_3_Rest_2_Ziffer | Div_3_Rest_2_Zahl Div_3_Rest_1_Ziffer
    Div_3_Rest_1_Zahl := Div_3_Rest_1_Ziffer | Div_3_Rest_1_Zahl Div_3_Rest_0_Ziffer | Div_3_Rest_2_Zahl Div_3_Rest_2_Ziffer | Div_3_Rest_0_Zahl Div_3_Rest_1_Ziffer
    Div_3_Rest_2_Zahl := Div_3_Rest_2_Ziffer | Div_3_Rest_2_Zahl Div_3_Rest_0_Ziffer | Div_3_Rest_0_Zahl Div_3_Rest_2_Ziffer | Div_3_Rest_1_Zahl Div_3_Rest_1_Ziffer
    

    Das selbe lässt sich natürlich auch direkt für 6 machen.



  • Es ist mal wieder soweit, das Semester scheint begonnen zu haben. Seufz, wie waers mal mit selber denken und Glueck verschenken.

    die Zahlen erstellt, bei denen die Quersumme 3 ergibt, oder eine Grammatik die gerade Zahlen konstruiert.

    Beides und dann bildest du den Schnitt der Mengen.

    Grammatik die gerade Zahlen konstruiert

    Das sollte trivial sein.

    bei denen die Quersumme 3

    Vorschlag: Baue einen endlichen Automaten fuer durch 3 teilbare Zahlen. Sollte nur 3 Zustaende besitzen. Mache eine Grammatik draus.



  • knivil schrieb:

    Vorschlag: Baue einen endlichen Automaten fuer durch 3 teilbare Zahlen. Sollte nur 3 Zustaende besitzen. Mache eine Grammatik draus.

    Will sehen.



  • Dachte das ist sehr aehnlich zu deinem Vorschlag. Hier nur schemenhaft dargestellt, da mir 10 Ziffern zu viele Pfeile werden.

    Zustand 0: bisherige Quersumme mod 3 = 0 <- akzeptierend
    Zustand 1: bisherige Quersumme mod 3 = 1
    Zustand 2: bisherige Quersumme mod 3 = 2

    Zustandsuebergaenge durch Ziffern respektieren Quersumme bisheriger eingelesener Ziffern.

    Zustand 0:
    '0': 0->0
    '1': 0->1
    '2': 0->2
    '3': 0->0
    ...

    Zustand 1: es fehlt also nur eine 2, 5, 8 um wieder Rest 0 zu haben
    '0': 1->1
    '1': 1->2
    '2': 1->0
    '3': 1->1
    ...

    Zustand 2: es fehlt nur eine 1, 4, 7 um wieder auf Rest 0 zu kommen
    ...

    Idee klar? Leider habe ich das ganze nicht formal durchgefuehrt und die Idee kann Ecken und Kanten haben. Das als Grammatik ist dann auch sehr viel Schreibarbeit und die spare ich mir.



  • Ach so meinst du das. OK. Das geht dann. 🙂

    Ich dachte mir, wenn ich einen "Automaten" basteln würde, der guckt ob irgend eine Zahl restfrei durch eine andere zu dividieren geht...
    ...dann würde ich keinen klassischen "Automaten" bauen, sondern die Zahl einfach mal parsen und dann gucken ob bei mod 3 auch 0 rauskommt.
    Man hätte also als Teil des Zustands einen "Akkumulator" der die aktuell geparste Zahl enthält.
    Also einfach so wie man es halt auch in echt programmieren würde.

    Und sowas dann in eine Grammatik zu überführen ... wüsste nicht wie das geht.


Log in to reply