BNF-Grammatik für Dualzahlen

Guten Abend,

ich sitze gerade an einer Aufgabe für meine Informatik-Vorlesung und stehe ziemlich auf dem Schlauch.

Es soll eine Grammatik in BNF-Form erstellt werden die Dualzahlen aktzeptiert deren Quersumme (ohne Rest) durch 3 teilbar ist.

also z.B.

111
1011
11101110

Gut, die höchstwertige Stelle muss immer 1 sein, aber ich weiß überhaupt nicht wie ich da weitermachen soll, würde mich über Denkanstöße freuen

Grüße

SeppJ

Erster Gedanke:

QuersummeDurchDreiTeilbar := <DreiEinsen><Rest>
Rest := | <DreiEinsen><Rest>
DreiEinsen := <Nullen> 1 <Nullen> 1 <Nullen> 1 <Nullen>
Nullen := | <Nullen> 0

Ist noch nicht sehr elegant von den Bezeichnern her, aber geht in die richtige Richtung. Du musst noch überlegen, ob du (wie hier) führende Nullen zulassen willst oder ob eine einzige 0 ebenfalls eine gültige Zahl ist. Diese Anpassungen überlasse ich mal dir, mein Vorschlag ist nur als Ansatz zu sehen.

Habs in der Zwischenzeit in der erweiterten BNF hingeschrieben, fand ich dann doch einfacher für den Ansatz.

<Zahl>    ::= <Ziffern> | <Zahl><Ziffern>
<Ziffern> ::= [<nullen>] <eins> [<nullen>] <eins> [<nullen>] <eins> [<nullen>]
<nullen>  ::= {<null>}+
<null>    ::= 0
<eins>    ::= 1

... also so ähnlich wie bei dir, vielen Dank!