Dein Fortschritt:
0 / 0 Aufgaben
1
Programme für einen Lernroboter
13 BEAFB I–IIEin Lernroboter versteht kurze Programme aus den Befehlen v (vorwärts), l (links drehen), r (rechts drehen) und der Wiederholung w( … ), die ihren Inhalt zweimal ausführt. Die erlaubten Programme beschreibt die Grammatik GR:
- N =
- {S, B}
- T =
- {v, l, r, w, (, )}
- Startsymbol:
- S
- Produktionsregeln:
- S → BS | B
B → v | l | r | w(S)
- Beschreiben Sie die Bedeutung der Nichtterminale S und B im Kontext des Roboters. (2 BE)
- Stellen Sie eine Linksableitung des Programms
vw(lv)dar. Geben Sie bei jedem Schritt die verwendete Regel an. (4 BE) - Zeichnen Sie den Ableitungsbaum zu
vw(lv). (4 BE) - Begründen Sie, dass
w()undvv)nicht zu L(GR) gehören. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Was lässt sich aus B ableiten, was aus S?
Hinweis zu Aufgabe b)
Ersetzen Sie immer das am weitesten links stehende Nichtterminal. Das Programm besteht aus zwei Befehlen, v und w(lv).
Hinweis zu Aufgabe c)
Jeder Ableitungsschritt erzeugt Kinder unter dem ersetzten Nichtterminal — in der Reihenfolge der rechten Seite.
Hinweis zu Aufgabe d)
Kann S zu ε werden? Wie entstehen Klammern?