reguläre Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:24 Di 09.04.2013 | | Autor: | bandchef |
| Aufgabe | Definieren sie eine Grammatik G mit der folgenden Eigenschaften:
G erzeugt alle Ziffernfolgen, deren Dezimalwert durch 6 teilbar ist. |
Hi Leute!
Eine natürliche Zahl die durch 6 teilbar ist, ist immer dann durch 6 teilbar wenn, die Quersumme der Zahl gerade durch 3 Teilbar ist und die Zahl an ihrer niederwertigsten Stelle eine 0, 2, 4, 6, oder 8 stehen hat; sprich, dass sie gerade ist.
Eine Grammatik zu erstellen, die eine Zahl erzeugt deren Quersumme durch 3 teilbar ist, hab ich mittlerweile. Eine Grammatik die ein gerade Zahl erstellt hab ich auch. Jetzt muss es doch irgendwie möglich sein, diese beiden Grammatiken zusammenzuführen, um zu einer Grammatik zu kommen, die meiner Anforderung entspricht...
Aber genau da hab ich mein Probleme! Kann mir jemand helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:33 Di 09.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
bevor ich mir weitere Gedanken mache: Ich gehe mal davon aus, dass führende 0en erlaubt sind? Gilt auch das leere Wort als Ziffernfolge, deren Dezimalwert durch 6 teilbar ist?
Viele Grüße
Tobias
|
|
|
| |
|
Ich weiß was du meinst. Führende Nullen sind nicht erlaubt. Auch ist kein bestimmter Grammatik-Typ vorausgesetzt. Somit können wir uns wohl auch aussuchen, ob das leere Wort als durch 6 teilbar gilt... Genau geht das aber aus der Aufgabenstellung leider nicht hevor...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:50 Mi 10.04.2013 | | Autor: | tobit09 |
> Ich weiß was du meinst. Führende Nullen sind nicht
> erlaubt. Auch ist kein bestimmter Grammatik-Typ
> vorausgesetzt. Somit können wir uns wohl auch aussuchen,
> ob das leere Wort als durch 6 teilbar gilt... Genau geht
> das aber aus der Aufgabenstellung leider nicht hevor...
OK, ich gehe dann ab jetzt davon aus, dass das leere Wort nicht als Ziffernfolge mit irgendeinem Dezimalwert gilt, aber das Wort 0 sehr wohl als Ziffernfolge mit durch 6 teilbarem Dezimalwert.
Deine Analyse aus dem Ausgangsposting, wann eine Zahl durch 6 teilbar ist, war völlig korrekt! 
Ich lasse die Frage mal nur teilweise beantwortet, vielleicht weiß ja jemand eine elegantere Lösung als ich.
Vorschlag: Die Grammatik so basteln, dass bei jeder Ableitung zunächst die hinterste Ziffer festgelegt wird, dann die vorderste Ziffer (wenn die Zahlenfolge aus mehr als einer Ziffer besteht) und schließlich von vorne nach hinten alle mittleren Ziffern.
Du könntest Nichtterminale in folgenden Bedeutungen verwenden:
S Startsymbol
A, B, C stehen für die vorderen Teile der gesuchten Ziffernfolge ohne die Endziffer, wobei A für einen Teil mit durch 3 teilbarer Quersumme steht, B für einen Teil mit "durch 3 teilbarer Zahl + 1" als Quersumme und C für einen Teil mit "durch 3 teilbarer Zahl + 2" als Quersumme.
A', B', C' stehen in ähnlicher Weise für die mittleren Teile der gesuchten Ziffernfolge.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:07 Mi 10.04.2013 | | Autor: | bandchef |
Ich hab dann mal auf dienen Ratschlag gehört, allerdings noch ein weitere Nichtterminal eingeführt das H. Das H steht für hinten.
S->0, S->AH
H->0, H->2, H->4, H->6, H->8
A->3B | 6B | 9B | 1C | 4C | 7C | 2D | 5D | 8D
B->0B | 3B | 6B | 9B | 1C | 4C | 7C | 2D | 5D | 8D | eps
C->0C | 3C | 6C | 9C | 1D | 4D | 7D | 2B | 5B | 8B
D->0D | 3D | 6D | 9D | 1B | 4B | 7B | 2C | 5C | 8C
Das sind nun die beiden Grammatiken von mir und der Vorschlag von dir miteinander verquickt. Irgendwie sieht das für mich etwas zu kompliziert...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:27 Mi 10.04.2013 | | Autor: | tobit09 |
> Ich hab dann mal auf dienen Ratschlag gehört, allerdings
> noch ein weitere Nichtterminal eingeführt das H. Das H
> steht für hinten.
>
> S->0, S->AH
> H->0, H->2, H->4, H->6, H->8
> A->3B | 6B | 9B | 1C | 4C | 7C | 2D | 5D | 8D
> B->0B | 3B | 6B | 9B | 1C | 4C | 7C | 2D | 5D | 8D | eps
> C->0C | 3C | 6C | 9C | 1D | 4D | 7D | 2B | 5B | 8B
> D->0D | 3D | 6D | 9D | 1B | 4B | 7B | 2C | 5C | 8C
>
> Das sind nun die beiden Grammatiken von mir und der
> Vorschlag von dir miteinander verquickt.
So in der Art habe ich mir das tatsächlich vorgestellt.
(B, C und D nehmen bei dir die Rolle ein, die ich für A', B' und C' vorgesehen hatte.)
Dass bei dir die 6 nicht ableitbar ist, kannst du leicht z.B. durch explizites Hinzufügen von S->6 korrigieren.
Das eigentliche Problem: Du berücksichtigst bei der Quersummenbildung die letzte Ziffer nicht.
Wenn du meinem Vorschlag folgst, muss sozusagen bei der Bildung der letzten Ziffer danach unterschieden werden, welchen Rest sie bei Teilen durch 3 hat.
Dafür hatte ich die Symbole A, B und C vorgesehen, während du nur das Symbol A verwendest.
> Irgendwie sieht
> das für mich etwas zu kompliziert...
Ich bin auch noch am Rätseln, ob das auch einfacher geht.
Wie lautet denn deine Grammatik "für Quersumme 3"? Ist sie wesentlich einfacher?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Fr 12.04.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
