Reguläre Grammatik mit rechtslinearen Produktionen erstellen |
| 28.02.2018, 09:29 | Auf diesen Beitrag antworten » |
| GastUser | Reguläre Grammatik mit rechtslinearen Produktionen erstellen Hallo zusammen, ich stehe momentan bei einer Übungsaufgabe für mein Studium vor einem Problem. Teil 1 der Aufgabe bestand darin zu einer Sprache eine kontextfreie Grammatik zu erstellen. Den Teil habe ich ohne größere Probleme hinbekommen. Teil 2 der Aufgabe ist es nun, diese kontextfreie Grammatik ein eine reguläre Grammatik umzuwandeln, die nur noch rechtslineare Produktionen enthält. Die Sprache gibt vor, dass Zeichenketten mit genau einem Kleinbuchstaben beginnen und daraufhin beliebig viele, aber mindestens eine Ziffer folgen. Danach ein Bindestrich und der Buchstabe A für Artikel. Basierend darauf sehen meine Produktionen so aus: Artikelnummer -> Kleinbuchstabe Ziffern - A Kleinbuchstabe -> a|...|z Ziffern -> Ziffer Ziffern | Ziffer Ziffer -> 0|...|9 Wenn ich daraus nun rechtslineare Produktionen bilden möchte, stehe ich vor dem Problem, dass Ziffern rekursiv ist. Und da beliebig viele Ziffern nach dem Kleinbuchstaben möglich sein sollen, komme ich um die auch nicht drum herum. Korrekt? An der Stelle komme ich nun also nicht mehr weiter. Eine rechtslineare Produktion muss das Nichtterminal ja immer rechts von einem Terminal stehen haben. Aber wie mache ich das nun mit Ziffern? Ich würde mich sehr freuen, wenn mir jemand weiterhelfen und mich in die richtige Richtung schubsen könnte. Danke schon mal und liebe Grüße! |
|
|
|
|
|
