extrem schwer zu findende formale Grammatik |
18.04.2012, 22:26 | Grammatika | Auf diesen Beitrag antworten » |
extrem schwer zu findende formale Grammatik Ich suche eine formale Grammatik der Sprache L={a^((2^n)-1), n>0 ist eine natürliche Zahl}, d.h. der Anzahl von genau 2^n-1 'a' -> z.B. a oder aaa oder aaaaaaa oder a^15 oder a^31 G = (V; Sigma, P, S) Sigma = {a} Das Problem lässt sich offensichtlich nicht als Typ2 Grammatik lösen -> d.h. muss es eine kontextabhänigge Grammatik sein. Vermutlich sogar eine Typ 0 Grammatik. Mein Ansatz wäre so etwas wie: S -> LCaNNNR L... linker Rand C... "Cursor" der vom linken zum rechten Rand laufen kann und Elemente verarbeitet, also z.B. Ca -> aC, CN-> aNC N... zu verarbeitende Elemente R... rechter Rand |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|